Я знаю, что есть n листьев на дереве, сколько возможных деревьев?

Question

Я знаю, что на дереве есть n листьев, Сколько возможных деревьев? Дерево может быть произвольно разветвленным (не менее 2-х веток).

Answer 1

ВАШЕ исходное помещение:

• у дерева n листьев
• дерево произвольно разветвленное

Вопрос: сколько возможных деревьев?

Ответ: бесконечно много.

Демонстрация:

Базовый корпус:

1 leaf:  (leaf)<---(node)
         (leaf)<---(node)<---(node)
         (leaf)<---(node)<---(node)<----(node)
         // and so on

Инкрементальный случай: n + 1 лист: То же, что и раньше, но добавить еще n листьев к родителю предыдущего листа

Answer 2

Определенно нет бесконечного множества деревьев, как предлагалось в предыдущем ответе.

Все комбинаторные объекты имеют конечную структуру и деревья с ограниченным количеством листьев.

«Демонстрация» ничего не говорит о бесконечности. Это просто показывает, что у нас есть прирост количества деревьев, если n увеличивается. Но n - конечное натуральное число. Суммирование натуральных чисел дает натуральное число, если количество членов суммы является натуральным числом. Я думаю, что для ответа на этот вопрос мы можем попробовать http://en.wikipedia.org/wiki/Generating_function. Но я не пользуюсь им каждый день и не могу быстро дать ответ.