Торт

[sergey1]

Подскажите пожалуйста идею.
Сколькими способами можно разрезать n-угольный выпуклый торт k непересекающимися диагоналями на куски?

В качестве ответа годится не только явная, но и рекурентная формула (по этой задаче надо составить программу).

[Руст]

Как понимать непересекающиеся диагонали. Могут ли они пересекаться на границе, т.е. выходит из одной вершины? Ответ зависит от этого.

[sergey1]

Диагонали можно проводить из одной вершины, нельзя, чтобы они пересекались внутри торта.

[Cube]

Иными словами: сколько можно сделать треугольников из n-угольника с помощью k диагоналей ?
Идея такая: каждая диагональ, проведённая из вершины i в вершину i+2 превращает n-угольник в (n-1)-угольник и уменьшает количество вариантов разрезания для вершины i+2 на 1 (а также, уменьшает на 1 количество доступных "к использованию" диагоналей). Из каждой многоугольника можно провести n-3 диагоналей. Треугольный торт уже никак не порезать, четырёхугольный - двумя способами при единственно возможном k=1.
В общем, получается что-то вроде

$$f(n,0)=0$$$$f(n,1)=2$$$$f(3,k)=0$$$$f(n,k)=\frac {n(n-3)} {2}f(n-1,k-1)$$

[Руст]

Во первых куски не обязательно треугольники. Ещё один вопрос на уточнение. Считаются ли одинаковыми разбиения полученные добавлением номерам вершин диагонали некоторой величины по модулю n (при нумерации, 0,1,...n-1). Например при правильной форме (торт - правильный n угольник) соответствующие куски одинаковые по объёму и форме, а для неправильного многоугольника можно говорит только, что соответствующие куски имеют то же количество вершин.

[sergey1]

Руст писал(а):

Во первых куски не обязательно треугольники. Ещё один вопрос на уточнение. Считаются ли одинаковыми разбиения полученные добавлением номерам вершин диагонали некоторой величины по модулю n (при нумерации, 0,1,...n-1). Например при правильной форме (торт - правильный n угольник) соответствующие куски одинаковые по объёму и форме, а для неправильного многоугольника можно говорит только, что соответствующие куски имеют то же количество вершин.

Разрезания считаются различными, если они различаются хотя бы одним разрезом.
Все вершины фиксированы, т.е. разрез, соединяющий вершины p и q и разрез, соединяющий вершины p+i и q+j - всегда различны.

[Cube]

Руст писал(а):

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

Для всякого n найдётся такое k, что в разбиении найдётся хотя бы один треугольник.
А чтобы посчитать нетреугольные куски, можно увеличить n на 1.
Что-то вроде
$f(n,k)=\frac {(n+1)(n-2)} {2}f(n,k-1)$
Понятное дело, за вычетом количества тех кусков, которые нам в таком случае не нужны.

[Руст]

В принципе ответы зависят только на множитель n при k>0. Поэтому будем считать, что различаются и обозначим это количество через функцию f(n,k). Берём одну диагональ, пусть она соединяет две вершины с номерами p и q. Ясно, что |p-q|>1 можеть быть взято произвольным нумерацию и разницу считаем по модулю n. Соответственно f(n,k) будет равна сумме по всем выбором этих вершин, а внутри сумма по m от произведений f(|p-q|+1,m)*f(n-|p-q|+1,k-1-m), m пробегает от 0 до m. При этом имеем f(n,0)=0, n<3, f(n,0)=1 при n>=3.
Этого достаточно для программирования. Ограничение |p-q|>1 снимается (можно не обращать внимания) за счёт f(n,0)=0 при n<=2.

[Руст]

Вообще то так придётся ещё учитывать нумерацию диагоналей. Поэтому лучше учитывать что имеется два самых внешних (левой и правой) диагоналей и индукцию лучше делать вырезанием их. Достаточно вырезать самую левую с номерами вершин p<q. Эта означает, что все остальные вершин диагоналей из интервала [p,q]. Таким образом, f(n,k)=cумма по p<q f(q+1-p,k-1). f(n,0)=1, n>=3, иначе 0. Например отсюда f(n,1)=C(n,2)-n=C(n-1,2).

[sergey1]

Руст

Спасибо. Выглядит правдоподобно. Буду додумывать.

[Руст]

Окончательно можно записать
f(n,k)= сумма по m (от 2 до n-2) (n-m)*f(m+1,k-1). Отсюда в частности получается f(n,1)=n(n-3)/2
Например f(n,2)= сумма (n-m)*(m+1)(m-2)/2=(n-3)(n-4)(n^2+25n-2)/24 (Здесь не уверен, что f(n,2) вычислил правильно)

[bot]

Cube писал(а):

Иными словами: сколько можно сделать треугольников из n-угольника с помощью k диагоналей ?

Количество разбиений выпуклого n-угольника на треугольники непересекающимися диагоналями - это (n-2)-е число Каталана.

Руст писал(а):

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

В этом вопрос?

[Руст]

Вообще и эта формула неверна. Окончательная ещё проще (заметил из-за отсутствия делимости на n). Вот окончательная рекурентная формула:
f(n,k)=(n/2)[f(k+1,k-1)+f(k+2,k-1)+ ...+f(n-1,k-1)]. Выбор первой точки n вариантов, выбор второй точки (суммирование) и учёт (левой или правой, в случае 1 ориентации) дает деление на 2. Мне кажется отсюда можно получить явный вид. Посмотрите на этот счёт "Конкретную математику", там есть похожие примеры. В частности при k=1 запишем полученное выражение в виде С(n-1,2)-C(n-3,0) (считаем, что С(0,0)=1). Просуммировав (учитывая то, что С(к-1,r-1)=C(k,r)-C(k-1,r)) получается формула f(n,2)=(n/2)(C(n-1,3)-C(n-3,1))=2C(n,4)-n(n-3)/2. Так получается, что главный член имеет вид k!C(n,2k).

[Руст]

Можно доказать, что f(n,k)<=k!C(n-2+k,2k) и получить формулу:
f(n,k)=k!C(n-2+k,2k)-сумма по 1<=r<=2k от выражения a(k,r)C(n-2+k-r,2k-r). Здесь коэффициенты a(k,r) не зависят от n и могут быть вычислены через рекурентное соотношение: f(n,k)=(n/2)[f(k+2,k-1)+...+f(n-1,k-1)].