Комбинаторика. Вырезание прямоугольника из квадрата

[malahai]

Условие такое:
Сколькими способами из клетчатого квадрата $n \times n$ можно вырезать прямоугольник по границам клеток?
Примечание: Симметричные случаи считаются различными. В итоговом ответе не использовать суммирование последовательностей.

У меня следующее решение: Будем выбирать прямоугольники c левого верхнего угла. Кол-во способов выбрать $k$ клеток на левой стороне квадрата равно $\binom{n}{k}$. Аналогично, кол-во способов выбрать $i$ клеток на верхней стороне квадрата равно $\binom{n}{i}$. По правилам суммы и произведения получаем:

$$4\sum_{i=1}^{n} \sum_{k=1}^{n} \binom{n}{k} \binom{n}{i}$$

Четверка получается из-за того, что мы рассматривали только один угол, а их четыре.
Правильны ли мои рассуждения? И как мне избавиться от суммирования?

[Brukvalub]

А как в решении учитывается, что группа выбранных на стороне клеток должна быть "сплошной"?

[alhimikoff]

Прямоугольник задаётся диагональю двумя способами. Надо подсчитать число возможных диагоналей и поделить на 2.
Решение для n=2 - 9 прямоугольников, на 4 не делится...

[Brukvalub]

alhimikoff в сообщении #1079377 писал(а):

Прямоугольник задаётся диагональю двумя способами. Надо подсчитать число возможных диагоналей и поделить на 2.
Решение для n=2 - 9 прямоугольников, на 4 не делится...

Что это было?

[alhimikoff]

Brukvalub в сообщении #1079381 писал(а):

Что это было?

Всего $(n+1)^2$ точек, надо выбрать из них 2 точки так чтобы они задавали диагональ прямоугольника

[malahai]

А если так решать:
Будем обходить квадрат таким образом: Сначала идет первая(самая верхняя) строчка и самая первая клеточка строчки, затем к этой клеточке прибавляется следующая за ней в строчке (получается прямоугольник из двух клеточек) и так до конца строки. Здесь $n$ способов построить прямоугольники. Затем в этой же строчке начинаем уже с конца таким же образом: сначала прямоугольник образует самая последняя клеточка строки, затем две самые последние клеточки... Здесь уже будет $n - 1$ способ. Т.к. один прямоугольник в этих двух обходах у нас одинаков (это вся строчка). Получаем по правилу суммы для первой строки: $n + n - 1 = 2n - 1$ Дальше, делаем то же самое с двумя верхними строчками(первая и следующая за ней), здесь мы будем прибавлять не одну клеточку, а уже столбец из клеточек этих строчек. Продолжая этот процесс и используя то, что квадрат симметричный, получаем, что всего $(2n - 1)^{n} Способов$

[ET]

alhimikoff

а вы не забывайте исключить те "диагонали", которые не диагонали, потому что они параллельны сторонам квадрата, тогда все начнет делиться на нужное
А можно просто решить, сколькими способми из отрезка длины $n$ можно выбрать отрезок меньшей длины и возвести в квадрат

[Brukvalub]

alhimikoff в сообщении #1079382 писал(а):

Всего $(n+1)^2$ точек, надо выбрать из них 2 точки так чтобы они задавали диагональ прямоугольника

alhimikoff в сообщении #1079377 писал(а):

Решение для n=2 - 9 прямоугольников, на 4 не делится...

Выходит, диагональ прямоугольника может быть параллельна стороне квадрата?

[alhimikoff]

ET в сообщении #1079389 писал(а):

alhimikoff
а вы не забывайте исключить те "диагонали", которые не диагонали, потому что они параллельны сторонам квадрата, тогда все начнет делиться на нужное
А можно просто решить, сколькими способми из отрезка длины $n$ можно выбрать отрезок меньшей длины и возвести в квадрат

Я на это и намекаю, здесь же готовое решение нельзя приводить... Решение из первого поста сразу видно что неправильное из-за 4.

[ET]

(Оффтоп)

alhimikoff Извините, спутал вас с ТС