Условие:
Перечислить все способы разрезать n-угольник на треугольники, проведя n - 2 его диагонали. Вершины пронумерованы.

Нашёл алгоритм,который похож на нужный мне, но код по нему не знаю как написать (ламмер я! :-) ):
Дан выпуклый n-угольник (заданный координатами своих
вершин в порядке обхода). Его разрезают на треугольники диагона-
лями, для чего необходимо n-2 диагонали (докажите индукцией по
n). Стоимостью разрезания назовем сумму длин всех использованных
диагоналей. Найти минимальную стоимость разрезания. Число
действий должно быть ограничено некоторым многочленом от n. (Пе-
ребор не подходит, так как число вариантов не ограничено многоч-
леном.)

Решение. Будем считать, что вершины пронумерованы от 1 до n
и идут по часовой стрелке. Пусть k, l - номера вершин, причем
l>k. Через A(k,l) обозначим многоугольник, отрезаемый от нашего
хордой k--l. (Эта хорда разрезает многоугольник на 2, один из
которых включает сторону 1--n; через A(k,l) мы обозначаем дру-
гой.) Исходный многоугольник естественно обозначить A(1,n). При
l=k+1 получается "двуугольник" с совпадающими сторонами.

Через a(k,l) обозначим стоимость разрезания многоугольника
A(k,l) диагоналями на треугольники. Напишем рекуррентную формулу
для a(k,l). При l=k+1 получается двуугольник, и мы полагаем
a(k,l)=0. При l=k+2 получается треугольник, и в этом случае так-
же a(k,l)=0. Пусть l > k+2. Хорда k--l является стороной много-
угольника A(k,l) и, следовательно, стороной одного из тре-
угольников, на которые он разрезан. Противоположной вершиной i
этого треугольника может быть любая из вершин k+1,...,l-1, и ми-
нимальная стоимость разрезания может быть вычислена как

min {(длина хорды k--i)+(длина хорды i--l)+a(k,i)+a(i,l)}

по всем i=k+1,..., i=l-1. При этом надо учесть, что при i=k+1
хорда k--i - не хорда, а сторона, и ее длину надо считать равной
0 (по стороне разрез не проводится).

Составив таблицу для a(k,l) и заполняя ее в порядке возрас-
тания числа вершин (равного l-k+2), мы получаем программу, ис-
пользующую память порядка n*n и время порядка n*n*n (однократное
применение рекуррентной формулы требует выбора минимума из не
более чем n чисел).

приведенный алгоритм находит не количество разбиений ,а стоимость минимального разбиения (сумма длин диагоналей)

Код

n - 3 S(n) = сумма S(2 + i)*S(n - i) + S(n - 1)        i = 1

количество разбиений равно сумме количества разбиений когда из первой вершины проведены хорды во все вершины от 3 до n - 1 плюс количество разбиений когда из первой вершины не проведено ни одной хорды.


ЗЫ
проверьте пожалуйста все ли учтено в формуле.

Это сообщение отредактировал(а) eskaflone - 5.11.2005, 22:38