Деревянная задача

[fregimus]

Возможно, что это классическая комбинаторная задача, но что-то никак не припомню, кто бы ее рассматривал. Меня некоторое время назад спросили об этом; ответа у меня не было. С тех пор я над ней думал время от времени.

Вопрос: сколько различных бинарных деревьев с n листьями можно построить? Обозначим число возможных деревьев как T(n).



Видно, что T(2)=1, T(3)=2, T(4)=5. А в общем виде? Лучше в закрытой форме, чем в рекуррентной, конечно.

Если просто помните решение, пока не говорите, но пообсуждать было бы очень интересно. Не уверен, что мой способ решения достаточно красив.

Comments

[kcmamu.livejournal.com]

Классическая.
Число правильных скобочных выражений.
Числа Каталана.

[fregimus.livejournal.com]

Спасибо. Интересно, у меня решение выражено иначе. Последовательность та же, разумеется.

На первый взгляд...

[fat-crocodile.livejournal.com]

Если n = 2^m, то одно.
Если n > 2^(m-1) и n = 2^m - k, то количество деревьев это количество способов выбрать k из 2^m. Т.е. C-из-2^m-по-k

Re: На первый взгляд...

[fat-crocodile.livejournal.com]

> Если n = 2^m, то одно.

Да, вот уже тут я не прав.

Re: На первый взгляд...

[fat-crocodile.livejournal.com]

И дальше неправ, т.к. правый или левый лист убирать -- не важно...

Catalan numbers

[falcao.livejournal.com]

Это числа Каталана, как уже говорилось выше. У них есть не менее десятка эквивалентных определений. То, которое рассмотрели Вы -- это одно из самых "прямых".

Удобнее в качестве параметра брать не число листьев, а число "кареток", то есть "ветвлений". Если таких "кареток" n, то "листьев" будет n+1. У Вас поэтому получается (n-1)-е число Каталана, обозначаемое c_{n-1}.

Для c_n общей формулой будет (2n)!/(n!(n+1))!; соответственно, в Вашем случае получается T(n)=(2n-2)!/((n-1)!n!) -- уже отсюда видно, что n удобнее изменить на единицу.

Доказательств у этой формулы также имеется очень много. Одно из них, имеющее скорее "фольклорное" происхождение, я как-то излагал на страницах математического сообщества:

http://community.livejournal.com/ru_math/382992.html

То, что там написано в Добавлении, можно перевести на геометрический язык. В Ваших обозначениях, если совсем коротко, получается следующее. Берём множество деревьев с n листами, у которых один из листов помечен. Мощность этого множества равна nT(n). Стянем в точку ту "каретку", которой принадлежит отмеченный лист, получая дерево с n-1 листом, у которого отметим ту вершину (уже не обязательно лист), которая осталась от стянутой "каретки". То множество, в которое мы отображаем, имеет мощность (2n-3)T(n-1) -- это множество деревьев с n-1 листом, у которых отмечена произвольная вершина.

Далее можно проверить, что у любого элемента при этом отображении имеется ровно 2 прообраза. Строятся они так: в том месте, где помечена вершина, делаем "расклейку", и одним из двух способов вставляем туда каретку, помечая у неё одну из концевых вершин, являющихся "листом". Это приводит к формуле nT(n)=2(2n-3)T(n-1), и далее итоговый результат получается уже чисто "арифметически".

[fregimus.livejournal.com]

Да, спасибо, интересно, сколько же разных способов решения. И результат по-разному записывается. У меня результат получился в виде



Тут хорошо видно, что он сверху ограничен, по меньшей мере, 4^{n-1}.

оценки сверху

[falcao.livejournal.com]

А каким способом Вы пришли к этому ответу, что Вы использовали? Понятно, что если значение гамма-функции от полуцелых чисел записать в явном виде, то возникнет то же самое выражение.

Что касается верхней оценки для c_n вида 4^n, то она в любом случае сразу видна. Ведь c_n = C_{2n}^n/(n+1), что не превышает C_{2n}^n. В свою очередь, по формуле бинома,

4^n=2^{2n}=(1+1)^{2n}=C_{2n}^0+C_{2n}^1+...+C_{2n}^n+...+C_{2n}^{2n} содержит С_{2n}^n в качестве слагаемого. То есть на самом деле отсюда можно извлечь такое неравенство:
c_n<=4^n/(n+1), верное при всех n>=0. В Ваших обозначениях, T(n)<=4^{n-1}/n.

А способов на самом деле очень много, включая те, где не надо ничего как бы "изобретать". Самое "тупое" доказательство, не требующее никакой "смекалки" или догадки, опирается на свойства так называемого "треугольника Каталана".

[fregimus.livejournal.com]

Через производящую функцию из рекуррентного представления Т(n) через предыдущие, как сумму попарных произведений T(k)T(n-k). Удивительно, что биномиальные коэффициенты у меня там не «вылезли» — вместо них зато образовался Покхаммеров символ. А гамма-функция появилась, когда я его раскрыл, чтобы сверху оценить это число. Я думал сначала, что рост быстрее экспоненциального будет, что-то вроде O(n^n). Но вывод какой-то длинный и неэлегантный получился.

"настоящий" бином Ньютона

[falcao.livejournal.com]

Рассуждение при помощи производящей функции, получаемой на основе рекуррентной формулы, является, наверное, одним из самых стандартных способов вывода формулы для чисел Каталана. Технически это несколько сложнее, но этот способ очень естественный. Я обычно в лекциях курса дискретной математики даю это рассуждение.

Мне кажется, биномиальные коэффициенты там возникают практически неизбежно в ходе подсчёта. А именно, поскольку доказательство опирается на разложение функции (1+x)^a в ряд Тейлора в окрестности нуля при a=1/2, то получаются коэффициенты вида C_{1/2}^n, которые далее выражаются через факториалы.

Кстати говоря, именно это дело и следовало бы называть "биномом Ньютона", так как считается, что для целых показателей формула была известна раньше, а заслуга Ньютона состоит в её распространение на случай нецелых показателей.

Я тут попутно придумал одно рассуждение, которое непосредственно даёт нужную формулу -- с использованием самых простых комбинаторных средств, без использования "трюка" со стягиванием кареток. Если хотите, могу его привести здесь.

[fregimus.livejournal.com]

Конечно, хочу! Пожалуйста.

ожерелья

[falcao.livejournal.com]

Есть очень полезное кодирование таких деревьев, на основе которого можно устанавливать полезные взаимно-однозначные соответствия. В частности, между скобочными выражениями разных типов. Есть как минимум два описания чисел Каталана при помощи скобочных выражений, где наличие соответствия напрямую не очевидно.

Код дерева строится так. Представьте себе, что Вы рисуете дерево слева. Есть некий "канонический" порядок это сделать. А именно, будущие "листы" добавляются слева направо, а каретка рисуется тогда и только тогда, когда уже появились те две вершины, на которые она опирается.

Например, как рисуется самое первое слева из пяти деревьев на Вашей картинке, где кареток ровно три? Порядок там такой:

лист
лист
каретка
лист
каретка
лист
каретка

Этот порядок полностью однозначен. Кодируя появление листа знаком +, а появления каретки знаком -, получаем коды каждого из деревьев. Я их сейчас выпишу -- для каждого из пяти случаев, считая слева направо.

++-+-+-
++++---
+++-+--
+++--+-
++-++--

В общем случае, если кареток n, то листьев n+1, и мы получаем код из n+1 плюса и n минусов с таким свойством: у любого начального отрезка кода, количество плюсов строго больше количества минусов. Это легко видно, если вдуматься в сам принцип построения кода, и означает то, что никакая каретка не может быть нарисована преждевременно. Довольно-таки понятно, что если дана последовательность плюсов и минусов с перечисленными выше свойствами, то какому-то дереву она точно соответствует.

Если понятно, как строится код, то теперь следующий шаг: плюсы и минусы располагаем по окружности по часовой стрелке. Получаются как бы ожерелья из белых и чёрных бусинок, где первых на единицу больше, чем вторых. Подсчёт числа таких ожерельев очень прост, поэтому сейчас надо убедиться, что при "зацикливании" не теряется информация. То есть что можно восстановить код по ожерелью -- узнать, в каком именно месте мы его замкнули.

(Ожерелья считаются "одинаковыми", если они отличаются поворотом; "зеркальные" отражения не допускаются.)

Проверить надо вот какой факт: если дано произвольное ожерелье из n+1 белых бусинок и n чёрных, то существует одно и только одно место, читая с которого, мы всегда будем получать на любом начальном отрезке строго больше белых бусинок нежели чёрных.

Прежде всего, почему таких мест не может быть два: если X -- промежуток от первого места до второго по часовой стрелке, а Y -- от второго к первому, тоже по часовой стрелке, то они покрывают окружность, и в каждом промежутке число белых бусинок больше. Но тогда общее число белых бусинок должно превышать число чёрных как минимум на два, что противоречит условию.

Далее, докажем, что существует такое место, чтение с которого всегда приводит к нужному нам результату. От противного: если это не так, то от любой точки при чтении по часовой стрелке есть промежуток, где белых бусинок не больше, чем чёрных. Начнём с произвольной точки, и каждый раз будем добавлять такой промежуток. В какой-то момент мы попадём в точку, где мы уже были. Это значит, что окружность обмотана такими промежутками по часовой стрелке один или более раз. Но из этого следует, что на окружности белых бусинок не больше, чем чёрных.

Таким образом, всё свелось к подсчёту числа ожерелий, но это уже "рутинная" комбинаторная задача. Если учесть тот факт, что каждое ожерелье с разных мест читается по-разному (а это, по сути, выше было уже проверено), то отметим одну из белых бусинок. Это можно сделать n+1 способом. Тогда ожерелью с отмеченной бусинкой соответствует набор из n плюсов и n минусов, причем это соответствие взаимно однозначно. Таких наборов ровно C_{2n}^n. Поэтому число ожерелий, а вместе с тем и число корневых двоичных деревьев с n каретками, равно C_{2n}^n/(n+1).
QED

Re: ожерелья

[fregimus.livejournal.com]

Чудесное просто решение! Одно удовольствие по нему пройти. Спасибо Вам. Такое школьнику запросто понятно. А у меня там гаммы с покхаммерами…

[bdag-med.livejournal.com]

Смешно, тут в процессе написания курсовой под моим руководством возник именно такой вопрос. Я не смог ответить, думал, по невежеству, я не математик ни разу. Оказывается, не все так просто :)

[fregimus.livejournal.com]

Ух, как интересно — Вы ведь археолог? Интересно, как в Вашей специальности такие вопросы возникают?

[bdag-med.livejournal.com]

Не, я филолог :)
А вопрос вот какой - языки классифицируются в виде деревьев, вот меня и спросили, сколько можно бинарных деревьев построить и как это считать. Именно в такой формулировке. В принципе, это был вопрос скорее теоретический, о природе вещей.
Вообще всякие комбинаторные задачи довольно часто возникают, хотя в самой элементарной форме, конечно.

[fregimus.livejournal.com]

Получается, что их число не больше 4ⁿ⁻¹. Это экспоненциальный рост, то есть ответ, совершенно серьезно, «много» — то есть, перебирать все возможные деревья непрактично даже для небольших n. Весьма плохой, в вычислительном смысле, случай.

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

[bdag-med.livejournal.com]

Ага.
Я как-то объяснял своей знакомой, сколько автомобильных номеров может быть теоретически. Она не могла поверить и стала выписывать их на бумажке... Плохо этому учат...

[cmike.livejournal.com]

Вообще-то попробовать руками – очень правильная идея. И математики об этом знают, как никто другой.

[cmike.livejournal.com]

Тут уже говорилось, что совпадает с числом правильных скобочных структур. Поскольку скобочная структура длины 4n−4 – строка той же длины в двузначном алфавите, то число не больше 4²ⁿ⁻². Оценко снизу 2ⁿ⁻² следует из того, что если в начале скобочной структуры поставить n−1 открывающих скобок, то следующие n−1 скобок можно поставить произвольно.

Это, конечно, очень грубо, зато "на пальцах" и становится сразу ясно, что какой-то экспоненциальный рост несомненно есть.

[fregimus.livejournal.com]

Да, действительно. Спасибо.

Куча информации о числах Каталана

[knop.livejournal.com]

...и "естественных отображениях" из одной комбинаторной их интерпретации в другую.
http://turgor.ru/lktg/2002/problem2.ru/index.php

Почитайте условия и решения, там действительно вагон всего.
Еще, кажется, потом на основе этой задачи была статья в "Мат.просвещении" (http://www.mccme.ru/free-books/matpros.html), но я не уверен.

Re: Куча информации о числах Каталана

[fregimus.livejournal.com]

Спасибо, отлично!