Комбинаторика, подсчет количества

[afternoon_sister]

Есть задача:

На клетчатой бумаге изображен квадрат, каждая сторона которого умещает ровно n клеток. Сколько в этом квадрате можно нарисовать различных букв "П"? Буквой "П" называется фигура не менее 3-ех клеток и две одинаковые ножки толщиной в одну клетку и длиной не менее 1-й клетки, соединяющиеся с перекладиной в любых двух ее точках, не являющихся соседними, а также повороты этой фигуры на 90, 180 и 270 градусов. Буквы, отличающиеся размерами и\или положением в клетчатом прямоугольнике считаются различными. Ответ необходимо представить в виде суммы, содержащей фиксированное количество слагаемых.

Мое решение:
1. ${n \choose 2}$ - количество способов выбрать длину буквы "П"
2. $\sum\limits_{k=3}^n {n-k+1 \choose 1} ({k \choose 2} - {k-1 \choose 1})$ - то есть сумма по длине верхней перекладины. Но никак не получается свести ее к сумме с фиксированным числом слагаемых. помогите разобраться плиз!

[provincialka]

Постановка задачи непонятная. Во-первых, как можно построить букву П из 3 клеток? По моему представлению, их надо не менее 5 (3 в перекладине и ножки по одной клетке)
Во вторых, что такое $n$? И каковы размеры прямоугольника? Или все-таки прямоугольником вы называете квадрат?

[afternoon_sister]

Да, извините, неправильно написала условие задачи.

$n$ - длина каждой стороны квадрата.
Буквой П называется фигура, имеющая верхнюю перекладину толщиной в одну клетку и длиной не менее трех клеток и две одинаковые ножки толщиной в одну клетку и длиной не менее 1-й клетки, соединяющиеся с перекладиной в любых ее двух точках, не являющихся соседними.

То есть, действительно для буквы П надо не менее пяти клеток.
Буквы П распологаем в квадрате со стороной $n$

[Sonic86]

afternoon_sister в сообщении #1154710 писал(а):

2. $\sum\limits_{k=3}^n {n-k+1 \choose 1} ({k \choose 2} - {k-1 \choose 1})$ - ... Но никак не получается свести ее к сумме с фиксированным числом слагаемых.

Раскройте биномиальные коэффициенты, получите степенные суммы. Как их считать - общеизвестно. (Вывод суммы не проверял)

[afternoon_sister]

Sonic86 в сообщении #1154773 писал(а):

afternoon_sister в сообщении #1154710 писал(а):

2. $\sum\limits_{k=3}^n {n-k+1 \choose 1} ({k \choose 2} - {k-1 \choose 1})$ - ... Но никак не получается свести ее к сумме с фиксированным числом слагаемых.

Раскройте биномиальные коэффициенты, получите степенные суммы. Как их считать - общеизвестно. (Вывод суммы не проверял)

Спасибо, а не могли ли вы просмотреть вывод этой суммы. Мне кажется, там все логично:
1. $$\sum\limits_{k=3}^n$ - сумма по всевозможным длинам верхней планки
2.${n-k+1 \choose 1}$ - выбрать место для этой планки из $n-k+1$ возможных
3. $ ({k \choose 2} - {k-1 \choose 1})$ - количество способов присобачить ноги к планке (вычитание ${k-1 \choose 1}$ - между ногами буквы должен быть просвет)

[provincialka]

А как вы учитываете,что фигуру можно вращать? Отраженная фигура совпадает с исходной?
Например, одинаковы ли фигуры
$\begin{matrix} H & H & H & H\\ & H & & H \end{matrix}$
и
$\begin{matrix} H & H & H & H\\ H & & H & \end{matrix}$
И вообще хотелось бы поподробнее, а то нам придется самим решать задачу, а не только проверять ваше решение.

-- 26.09.2016, 21:00 --

afternoon_sister в сообщении #1154808 писал(а):

(вычитание ${k-1 \choose 1}$ - между ногами буквы должен быть просвет)

Ну... можно и проще: если первая "ножка" стоит в левом конце, для остальных остается $k-2$ места, если на втором слева месте -- остается $k-3$ и т.д., всего $(k-2)+(k-3)+...+1 =\frac{(k-2)(k-1)}{2}$. Впрочем, можно и вашим способом считать. Здесь $k$ -- длина перекладины.

-- 26.09.2016, 21:02 --

И еще заметьте, что максимальная длина ножек меняется в зависимости от расположения перекладины в квадрате.

[afternoon_sister]

Вот более подробное решение:
В ответе будем просто перемножать 1*2*3:
1. 4 - отражает перевороты буквы на 90, 180, 270 градусов
2. ${n \choose 2}$ - выбираем 2 строки, где меньшая будет сигнализировать начало буквы П, а большая - конец.(то есть такие образом определим высоту и вертикальное размещение буквы П в квадрате.
3.$\sum\limits_{k=3}^n (n-k+1)*(k-1)*(k-2)/2$ - где $k$ - итерируем по длине горизонтальной планки, $n-k+1$ - количество способов разместить планку длиной k в квадрате со стороной n, $(k-1)*(k-2)/2$ - количество способов поставить ножки к планке длиной k.

Перемножив 1*2*3 получаем ответ на задачу

[provincialka]

Умножение пишите как \cdot.
Что такое "начало буквы" и "конец"? Почему они заданы одним числом?
Не лучше ли выбрать минимальный прямоугольник, вмещающий фигуру, а в нем уже проверять возможные расположения? (располагая перекладину по четырем сторонам).
Ох... лень что-то разбираться... А вы проверили ответ на небольших значениях $n$?

-- 26.09.2016, 23:59 --

Точно могу сказать, что 1 пункт верный. Потому что все фигуры можно разбить на классы "перекладина вертикальна, ножки вправо", "перекладина вертикальна, ножки влево", "перекладина горизонтальна, ножки вниз", "перекладина горизонтальна, ножки вверх", которые по числу элементов в них совпадают.

Но дальше я бы все-таки предложила рассматривать прямоугольник, в который вписана буква П. Вроде так удается "свернуть" ответ.

[Lia]

Аккаунт afternoon_sister блокируется по выбору пользователя в связи с регистрацией клона stanger.
stanger, строгое предупреждение за двойную регистрацию.