Форум умных людей

Пусть у нас есть треугольник из точек, аналогичный тем, что на рисунке.

(http://www.likebook.ru/store/pictures/182/182492/3.png)

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

1) Каждая точка, кроме корневой (единственной точки первого яруса), должна быть соединена ровно с одной точкой предыдущего яруса.
2) Каждая точка может соединяться с нулём, одной либо двумя точками следующего яруса, причём лишь с ближайшими (k-я точка на n-м ярусе может быть соединина лишь с k-й и (k+1)-й точками на (n+1)-м ярусе).
3) Никаких соединений, кроме предусмотренных правилами 1),2), быть не должно.

Получившийся граф (он, кстати, будет бинарным деревом) мы назовём треугольным деревом порядка N, где N - количество ярусов в нашем точечном треугольнике.

Сколько существует различных треугольных деревьев порядка 13?

таки да

А можно доказательство?

Ну, пожалуйста! :girlcry:

Sirion, уточните, пожалуйста, условие. Что вы понимаете под "различными треугольными деревьями"?

Какой из вариантов задачи вы имеете в виду?

    А     Б     С    Д
    /      \      /     \
   /        \     \     /\

а) А,Б,С,Д все разные
б) А = Б, но  А не равно С и Д
с) А = Б = С, но А не равно Д

Скорее всего вы имеете в виду самый естественный вариант а)
Но тогда приведённая выше формула не получается.
Для порядков 3 и 4 можно перебрать все варианты "на пальцах", дальше надо писать программу.
В варианте а) вроде бы получаются числа:
1) 1
2) 3
3) 17
4) 175
и т.д.

Задача на программирование интересная, особенно для порядка 13 и выше.
Но почему вы поместили её в "математические задачи"?
Интересно посчитать количество деревьев для варианта с).
Но всё это для раздела "задачи для программистов".

Каждая внутренняя точка N-го яруса (начиная с 3-го) может быть соединена с одной из 2-х точек предыдущего (N-1)-го яруса. Всего для (N-2)-х точек N-го яруса получаем 2^N-2  вариантов.
Всего для всех 13 ярусов получаем 2^3-2*2^4-2*...*2^13-2=2^1+2+...+11=2^11*12/2.

Ну да, невнимательно прочитал условия. Упустил что "Каждая точка ... должна быть соединена". Я думал что какие-то точки можно оставить пустыми. Спасибо за ответ. Кстати, если разрешить такие "пустые" точки, получается интересная задача на программирование. Лобовое решение для уровня 13 и выше работает долго, надо что-то придумывать. Помещу-ка её в программистский раздел.

Треугольное дерево 2 (http://nazva.net/forum/index.php/topic,8591.0.html)