2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:32 


23/11/15
11
Условие такое:
Сколькими способами из клетчатого квадрата $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 
Заслуженный участник
Аватара пользователя


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

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


27/11/15

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

 Профиль  
                  
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 12:56 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
alhimikoff в сообщении #1079377 писал(а):
Прямоугольник задаётся диагональю двумя способами. Надо подсчитать число возможных диагоналей и поделить на 2.
Решение для n=2 - 9 прямоугольников, на 4 не делится...

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

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


27/11/15

115
Brukvalub в сообщении #1079381 писал(а):
Что это было? :shock:

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

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


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

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


08/05/08
593
alhimikoff

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

 Профиль  
                  
 
 Re: Комбинаторика. Вырезание прямоугольника из квадрата
Сообщение04.12.2015, 13:23 
Заслуженный участник
Аватара пользователя


01/03/06
13626
Москва
alhimikoff в сообщении #1079382 писал(а):
Всего $(n+1)^2$ точек, надо выбрать из них 2 точки так чтобы они задавали диагональ прямоугольника

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

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

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


27/11/15

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

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

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


08/05/08
593

(Оффтоп)

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 10 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group