2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:32 
Условие такое:
Сколькими способами из клетчатого квадрата $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}$$
Четверка получается из-за того, что мы рассматривали только один угол, а их четыре.
Правильны ли мои рассуждения? И как мне избавиться от суммирования?

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:48 
Аватара пользователя
А как в решении учитывается, что группа выбранных на стороне клеток должна быть "сплошной"?

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

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:56 
Аватара пользователя
alhimikoff в сообщении #1079377 писал(а):
Прямоугольник задаётся диагональю двумя способами. Надо подсчитать число возможных диагоналей и поделить на 2.
Решение для n=2 - 9 прямоугольников, на 4 не делится...

Что это было? :shock:

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:58 
Brukvalub в сообщении #1079381 писал(а):
Что это было? :shock:

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

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

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 13:20 
alhimikoff

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

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 13:23 
Аватара пользователя
alhimikoff в сообщении #1079382 писал(а):
Всего $(n+1)^2$ точек, надо выбрать из них 2 точки так чтобы они задавали диагональ прямоугольника

alhimikoff в сообщении #1079377 писал(а):
Решение для n=2 - 9 прямоугольников, на 4 не делится...

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

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 13:25 
ET в сообщении #1079389 писал(а):
alhimikoff
а вы не забывайте исключить те "диагонали", которые не диагонали, потому что они параллельны сторонам квадрата, тогда все начнет делиться на нужное
А можно просто решить, сколькими способми из отрезка длины $n$ можно выбрать отрезок меньшей длины и возвести в квадрат

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

 
 
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 13:44 

(Оффтоп)

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

 
 
 [ Сообщений: 10 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group