Деревья. Правильно ли работает программа!

[Serge_Bliznykov]

корень и еще одна вершина, соединенная с ним

по условию задачи такое не допустимо.

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

[Poma][a]

по условию задачи такое не допустимо.

Мда.. Разбилась моя теория.. Надо все же иногда читать условие. Спасибо!

И тогда я вообще против такого.. Это отход от истинного дерева.. Ересь..

[Poma][a]

Тогда вот так http://oeis.org/A002628

[Базиля]

Сообщение от Serge_Bliznykov

согласен.
Только вот значение "потомок" в исходном посте TC совпадает со значением в определении (на вики, например): - это только "дети" (внуки и правнуки не участвуют в данном случае).

Я Вас понял

Сообщение от Poma][a

О решении : для начала я вынужден не согласиться с ТС. Для N = 2 возможны три варианта : один корень, корень и еще одна вершина, соединенная с ним, и полное бинарное дерево..

Ну в таком случае, исходя из того, что мы обсуждали выше, получаем 5 возможных вариантов для N = 2.
Не забываем, что по условию сказано

высота которых не превышает N

[Poma][a]

Ну в таком случае, исходя из того, что мы обсуждали выше, получаем 5 возможных вариантов для N = 2.
Не забываем, что по условию сказано
Цитата:

Откуда 5? Может быть еще 4.. Но не 5...
Если мы говорим об одной высоте.. Как я пониаю, на рисунке Сержа высота =4

[Базиля]

Сообщение от Poma][a

Откуда 5? Может быть еще 4.. Но не 5...

Именно 5

Сообщение от Poma][a

Как я пониаю, на рисунке Сержа высота =4

3

[Poma][a]

А ну тогда все ясно.. И мой ответ проходит. Только нужно искать для N+1

[Базиля]

Сообщение от Sibedir

f(n) = f(n-1)^2 + 1
вроде так, но не доказано.

Решил озадачить себя выводом формулы.
К успеху еще пока что не пришел
Но решил проверить Вашу формулу - для высоты 3 и ниже результаты вычислений верны (проверял вручную - в том смысле, что рисовал все варианты деревьев ).
Для остальных высот проверить правильность попросту не в состоянии.
Привожу результаты всех вычисления компьютером

Высота 0 = 1
Высота 1 = 2
Высота 2 = 5
Высота 3 = 26
Высота 4 = 677
Высота 5 = 458330
Высота 6 = 210066388901

Числа огромные, я бы даже и не подумал, что для дерева высотой 4 уже столько вариантов...
Хотелось бы узнать, из чего исходили при составлении формулы?
Ведь далеко не факт, что она верна ( именно на данный момент, не зная Вашей логики ее составления ), т.к. доказать на практике результаты для остальных вариантов не кажется возможным
Спасибо!

[Sibedir]

f(n-1) - кол-во вариантов справа
x
f(n-1) - кол-во вариантов слева
+
1 - еще один уровень
=
f(n-1)^2 + 1

комбинаторика

как-то так

----------------------------------------------------------
и еще
Высота 0 = 1
Высота 1 = 2
Высота 2 = 5
Высота 3 = 26
Высота 4 = 677
Высота 5 = 458330
Высота 6 = 210066388901
Высота 7 = 44127887745906175987802
Высота 8 = 1.9472704769152964495597034454938e+ 45
Высота 9 = 3.7918623102659260828682350280279e+ 90
Высота 10 = 1.4378219780015246281818710879551e+ 181
Высота 11 = 2.0673320404242167718163471873404e+ 362
Высота 12 = 4.2738617653645554487425669417955e+ 724

[Базиля]

Понял, спасибо!

и еще

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