Подсчет бинарных деревьев

Question

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

Просматривая страницу Википедии для Бинарные деревья, я заметил это утверждение о том, что количество корневых двоичных деревьев размером $ n $ было бы таким Каталонский номер:$$C_n = \dfrac{1}{n+1}{2n \выбрать n}$$

Но я не понимаю, как я мог сам прийти к такому результату?Есть ли способ найти этот результат?

Теперь, что, если порядок поддеревьев (что слева, что справа) не учитывается?Например, с моей точки зрения, я считаю, что эти два дерева - одно и то же:

   /\   /\
  /\     /\

Можно ли было бы применить аналогичный метод, чтобы подсчитать, сколько из этих объектов имеют ровно $ n $ узлов?

Answer 1

Для подсчета многих типов комбинаторных объектов, таких как деревья в этом случае, существуют мощные математические инструменты (символический метод), которые позволяют вам мехнически получать такие подсчеты из описания, как строятся комбинаторные объекты. Это включает в себя генерирование функций.

Отличная ссылка Аналитическая комбинаторика Покойный Филипе Фладжолет и Роберт Седжвик. Он доступен по ссылке выше.

Покойная книга Герберта Уилфа генерирующая функциология еще один бесплатный источник.

И конечно Бетонная математика от GKP - это сокровищница.

---

Для двоичных деревьев это так: сначала вам нужно четкое определение дерева.

Бинарное дерево-это коренящееся дерево, в котором каждый нелистный узел точно имеет степень 2.

Далее мы должны согласиться, как хотим позвонить размер дерева.

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

Теперь мы должны получить описание того, как строятся эти комбинаторные объекты. В случае бинарных деревьев рекурсивное разложение возможно.

Пусть $ mathcal {a} $ будет набором всех бинарных деревьев первого типа, а затем символически мы имеем:

Он читается как: «Объект класса бинарных деревьев - это либо узел, либо узел, за которым следует два двоичных деревья». Это может быть написано как уравнение наборов:

$$ mathcal {a} = { bullet } cup bigl ( { bullet } times mathcal {a} times mathcal {a} bigr) $$

Вводя функцию генерирования $ a (z) $, которая перечисляет этот класс комбинаторных объектов, мы можем перевести уравнение установки в уравнение, включающее генерирующую функцию.

$$ a (z) = z+za^2 (z) $$

Наш выбор обращения со всеми узлами одинаково и принимать количество узлов в дереве, поскольку понятие его размера выражается путем «маркировки» узлов с переменной $ z $.

Теперь мы можем решить квадратичное уравнение $ za^2 (z) -a (z)+z = 0 $ для $ a (z) $ и получить, как обычно, два решения, явную закрытую форму генерирующей функции:

$$ a (z) = frac {1 pm sqrt {1-4z^2}} {2Z} $$

Теперь нам просто нужна биномиальная теорема Ньютона:

$$ (1+x)^a = sum_ {k = 0}^ infty binom {a} {k} x^k $$

с $ a = 1/2 $ и $ x = -4z^2 $, чтобы расширить закрытую форму генерирующей функции обратно в серию мощности. Мы делаем это, потому что коэффициент $ Z^n $ - это лишь количество комбинаторных объектов размера $ n $, обычно написанных как $ [z^n] a (z) $. Но здесь наше представление о «размере» дерева заставляет нас искать коэффициент в $ z^{2n+1} $. После небольшого жонглирования биномиалами и факториалами мы получаем:

$$ [z^{2n+1}] a (z) = frac {1} {n+1} binom {2n} {n}. $$

Если мы начнем со второго понятия о размере, рекурсивное разложение:

Мы получаем другой класс комбинаторных объектов $ mathcal {b} $. В нем говорится: «Объект класса бинарных деревьев - это либо лист, либо межоверный узел, за которым следуют два двоичных деревья».

Мы можем использовать тот же подход и повернуть $ mathcal {b} = { square } cup bigl ( { bullet } times mathcal {b} times mathcal {b} bigr) $ в $ mathcal {b} = 1+zb^2 (z) $. Только на этот раз переменная $ Z $ только отмечает внутренние узлы, а не листья, потому что определение «размер» здесь отличается. Мы также получаем другую генерирующую функцию:

$$ b (z) = frac {1- sqrt {1-4z}} {2Z} $$

Извлечение доходности коэффициента

$$ [z^n] b (z) = frac {1} {n+1} binom {2n} {n}. $$

Класс $ mathcal {a} $ и $ mathcal {b} $ согласен с подсчетом, потому что двоичное дерево с внутренними узлами $ n $ имеет листья $ n+1 $, таким образом, в общей сложности 2n+1 $ узлы.

В последнем случае мы должны работать немного усерднее:

что является описанием бинарных попыток, не обрезленных. Мы расширяем это на $$ begin {Align} mathcal {c} & = { bullet } cup bigl ( { bullet } times mathcal {c} bigr) cup bigl ( { bullet } times mathcal {c} bigr) cup bigl ( { bullet } times mathcal {c} times mathcal {c} bigr) Mathcal {d } & = { epsilon } cup bigl ( { bullet } times mathcal {c} times mathcal {c} bigr) end {align} $$

и переписать его с генерацией функций

$$ begin {align} c (z) & = z+2zc (z)+zc^2 (z) d (z) & = 1+zc^2 (z) end {align} $$

Решить квадратичные уравнения

$$ begin {align} c (z) & = frac {1-2z- sqrt {1-4z}} {2z} d (z) & = frac {1- sqrt {1-4z }} {2Z} end {Align} $$

И снова получите

$$ [z^n] c (z) = frac {1} {n+1} binom {2n} {n} Quad n ge1 qquad [z^n] d (z) = frac { 1} {n+1} binom {2n} {n} Quad n ge0 $$

Обратите внимание, что Каталонская генерирующая функция является

$$ e (z) = frac {1- sqrt {1-4z}} {2} $$

это перечисляет класс Общие деревья. Анкет Это деревья без ограничений на степень узла.

$$ mathcal {e} = { bullet } times mathrm {seq} ( mathcal {e}) $$

Он читается как: «Объект класса общих деревьев - это узел, за которым следует возможная пустая последовательность общих деревьев».

$$ e (z) = frac {z} {1-e (z)} $$

С Лагранж-Бюрманн Формула инверсии мы получаем

$$ [z^n] e (z) = frac {1} {n+1} binom {2n} {n} $$

Таким образом, мы доказали, что существует столько общих деревьев, сколько и бинарных деревьев. Неудивительно, что существует биение между общими и бинарными деревьями. Биение известна как Вращающаяся соответствие (объяснено в конце связанной статьи), которая позволяет нам хранить каждое общее дерево как двоичное дерево.

Обратите внимание, что если мы не отличаем левого и правого брата в классе $ mathcal {c} $, мы получим еще один класс деревьев $ mathcal {t} $:

Единые бинарные деревья. $$ mathcal {t} = { bullet } times mathrm {seq} _ { le2} ( mathcal {t}) $$ Они также имеют генерирующую функцию тоже $$ t (z) = frac {1-z- sqrt {1-2Z-3Z^2}} {2Z} $$ Однако их коэффициент отличается. Вы получаете номера Motzkin $$ [z^n] t (z) = frac {1} {n} sum_k binom {n} {k} binom {nk} {k-1}. $$

О, и если вам не нравится генерировать функции, есть и другие доказательства. Видеть здесь, есть тот, где вы могли бы использовать кодирование бинарных деревьев в качестве слова Dyck и получить рецидив из их рекурсивного определения. Затем решение этого повторения дает ответ тоже. Однако символический метод спасает вас от того, что вы в первую очередь придумывают рецидив, так как он работает непосредственно с чертежом комбинаторных объектов.

Answer 2

Генерирующие функции - это очень мощная и очень полезная волшебная палочка.Следующее решение первого вопроса (почему существуют деревья $ C_n $) несколько менее волшебное.Следовательно, симпатичный.

Пример. Чтобы создать дерево из $ 5 $ узлов, мы начинаем с последовательности, в которой $ + 1 $ встречается $ 5 + 1$ раз, а $ -1 $ встречается $ 5$ раз.Например, $+-++-+--++-$.Среди префиксов с наименьшей (и, возможно, отрицательной) суммой выберите самый длинный;в данном случае, $+-++-+--$.Возьмите этот префикс из начала и поставьте его в конце;в этом случае мы получаем $++-+-++-+--$.Теперь измените $ + $ на $ T $ и $-$ на $ E $;в этом случае мы получаем TTETETTETEE.Удалите $ T $ из начала, добавьте $ E $ в конце;в этом случае мы получаем TETETTETEEE.Это описание дерева T(E,T(E,T(T(E,T(E,E)),E))).Ниже есть некоторое объяснение того, почему это биекция.Как только вы убедитесь в этом, подсчет станет легким делом.Существуют последовательности $ \ binom {5 + 6} {5} $ из $ \ pm1 $, затем мы разделили на $ 5 + 6 $, потому что выбрали одну из возможных циклических перестановок.

Первая биекция. Типичным определением для деревьев в ML является type tree = T of tree * tree | E;то есть дерево либо имеет два (упорядоченных) поддерева, либо оно пустое.Вот как строятся деревья: T(T(E,E),T(T(E,E),T(E,E))).Отбросив пух, мы можем просто написать TTEETTEETEE.Все подобные описания будут заканчиваться E, так что это избыточно: TTEETTEETE.(Обратите внимание, что пустое дерево теперь соответствует пустой строке.) Эти строки обладают тем свойством, что каждый префикс имеет по меньшей мере столько же Ts, сколько Es, и в общей сложности они имеют $ n $ Ts и $ n $ Es, где $ n $ - количество узлов дерева.

Вторая биекция. Теперь мы заменим T на +1, а E на -1.Итак, мы рассматриваем последовательности с $ n $ значениями +1, с $ n $ значениями -1 и с суммами всех префиксов $ \ge0 $.

Третья биекция. Теперь мы немного изменим требования к префиксам:Мы просим, чтобы сумма каждого непустого префикса была равна $> 0 $.Чтобы это было возможно, мы допустим $ n + 1 $ значений +1 и $ n $ значений -1.(В противном случае сумма всей строки была бы равна 0 и не соответствовала бы условию для префиксов.) Эти последовательности должны начинаться с +1.Итак, они действительно такие же, как и раньше, за исключением того, что в начале у них застрял +1.

Собственность Рейни. Теперь на мгновение забудьте о наших последовательностях и рассмотрим некоторую конечную последовательность целые числа $x_1$, $\ldots\,$, $x_m$, сумма которых равна 1.Если все непустые префиксы имеют положительные суммы, то никакая циклическая перестановка этой последовательности не обладает тем же свойством.Почему?Что ж, предположим, что существует $ k \ ne1 $ такое, что $ x_k, \ldots, x_m, x_1,\ldots,x_{k-1} $ также имеет все непустые префиксы положительные.Затем $x_1+\cdots +x_{k-1}\ge1$ (свойство последовательности, начинающейся с $ x_1 $) и $x_k +\cdots + x_m\ge1$ (свойство последовательности, начинающейся с $ x_k $);следовательно, $x_1+\cdots+x_m\ge2$, что противоречит предположению о том, что сумма для всей последовательности равна 1.

Более того, при заданной некоторой последовательности с суммой 1 всегда существует циклическая перестановка, которая приводит к тому, что все непустые префиксы имеют положительную сумму.(Это верно даже для действительных чисел.)

Заключение. Теперь давайте подсчитаем последовательности +1 и -1, которые находятся в биекции с деревьями.Из $ 2n + 1 $ чисел мы должны выбрать $ n + 1 $, которые равны +1, остальные будут равны -1.Есть $ {2n + 1 \ выберите n + 1} $ способы сделать это.Но только $ 1 $ из подсчитанных до сих пор последовательностей $ 2n + 1 $ имеет положительные префиксы.Итак, количество корневых упорядоченных двоичных деревьев равно:

$${1\превышение 2n+1}{2n +1\выбрать n+1}={1\превышение 2n+1}{2n+1\превышение n+1}{2n\выбрать n}={1\превышение n+1}{2n\выбрать n}$$