2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Торт
Сообщение14.02.2006, 11:33 


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

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

 Профиль  
                  
 
 
Сообщение14.02.2006, 11:52 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение14.02.2006, 12:05 


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

 Профиль  
                  
 
 Идея
Сообщение14.02.2006, 12:18 
Аватара пользователя


20/01/06
64
оттуда
Иными словами: сколько можно сделать треугольников из 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)$$

 Профиль  
                  
 
 
Сообщение14.02.2006, 13:33 
Заслуженный участник


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

 Профиль  
                  
 
 
Сообщение14.02.2006, 13:52 


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


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

 Профиль  
                  
 
 
Сообщение14.02.2006, 13:55 
Аватара пользователя


20/01/06
64
оттуда
Руст писал(а):
Во первых куски не обязательно треугольники...

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

 Профиль  
                  
 
 
Сообщение14.02.2006, 13:59 
Заслуженный участник


09/02/06
4339
Москва
В принципе ответы зависят только на множитель 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.

 Профиль  
                  
 
 
Сообщение14.02.2006, 14:34 
Заслуженный участник


09/02/06
4339
Москва
Вообще то так придётся ещё учитывать нумерацию диагоналей. Поэтому лучше учитывать что имеется два самых внешних (левой и правой) диагоналей и индукцию лучше делать вырезанием их. Достаточно вырезать самую левую с номерами вершин 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).

 Профиль  
                  
 
 
Сообщение14.02.2006, 14:44 


14/02/06
281
Руст

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

 Профиль  
                  
 
 
Сообщение14.02.2006, 15:18 
Заслуженный участник


09/02/06
4339
Москва
Окончательно можно записать
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) вычислил правильно)

 Профиль  
                  
 
 
Сообщение15.02.2006, 07:12 
Заслуженный участник
Аватара пользователя


21/12/05
5624
Новосибирск
Cube писал(а):
Иными словами: сколько можно сделать треугольников из n-угольника с помощью k диагоналей ?

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

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

 Профиль  
                  
 
 
Сообщение15.02.2006, 08:31 
Заслуженный участник


09/02/06
4339
Москва
Вообще и эта формула неверна. Окончательная ещё проще (заметил из-за отсутствия делимости на 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).

 Профиль  
                  
 
 
Сообщение15.02.2006, 13:45 
Заслуженный участник


09/02/06
4339
Москва
Можно доказать, что 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)].

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

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



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

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


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

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