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

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

Глядя на страницу Википедии о бинарных деревьях , я заметил это утверждение, что число корневых бинарных деревьев размером $n$ будет таким каталонским числом :

C_{n} = \frac{1}{n + 1} (\binom{2 n}{n})

$C_n = \dfrac{1}{n+1}{2n \choose n}$

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

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

   /\   /\
  /\     /\

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

combinatorics binary-trees discrete-mathematics Стефан Хименес
источник

Применима ли здесь теорема Поли о укорененных 2-арных деревьях?

Николас Манкузо

Ответы:

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

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

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

И, конечно, « Конкретная математика» от GKP - это клад.

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

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

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

введите описание изображения здесь

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

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

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

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

A = {∙} \cup ({∙} \times A \times A)

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

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

A (z) = z + z A^{2} (z)

$A(z)=z+zA^2(z)$

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

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

A (z) = \frac{1 \pm \sqrt{1 - 4 z^{2}}}{2 z}

$A(z)=\frac{1\pm\sqrt{1-4z^2}}{2z}$

Теперь нам просто нужна (обобщенная) теорема Ньютона:

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

$(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^{2 n + 1}] A (z) = \frac{1}{n + 1} (\binom{2 n}{n}) .

$[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 - 4 z}}{2 z}

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

Извлечение коэффициента урожайности

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

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

Классы и согласуются по количеству, потому что бинарное дерево с внутренними узлами имеет лист, таким образом, всего узел. $\mathcal{A}$ $\mathcal{B}$ $n$ $n+1$ $2n+1$

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

введите описание изображения здесь

который является описанием непустых сокращенных двоичных попыток. Мы расширяем это до

\begin{aligned} C & = {∙} \cup ({∙} \times C) \cup ({∙} \times C) \cup ({∙} \times C \times C) \\ D & = {ϵ} \cup ({∙} \times C \times C) \end{aligned}

$\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{aligned} C (z) & = z + 2 z C (z) + z C^{2} (z) \\ D (z) & = 1 + z C^{2} (z) \end{aligned}

$\begin{align}C(z)&=z+2zC(z)+zC^2(z)\\D(z)&=1+zC^2(z)\end{align}$

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

\begin{aligned} C (z) & = \frac{1 - 2 z - \sqrt{1 - 4 z}}{2 z} \\ D (z) & = \frac{1 - \sqrt{1 - 4 z}}{2 z} \end{aligned}

$\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{2 n}{n}) n \geq 1 [z^{n}] D (z) = \frac{1}{n + 1} (\binom{2 n}{n}) n \geq 0

$[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 - 4 z}}{2}

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

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

E = {∙} \times S E Q (E)

$\mathcal{E}=\{\bullet\}\times\mathrm{SEQ}(\mathcal{E})$

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

E (z) = \frac{z}{1 - E (z)}

$E(z)=\frac{z}{1-E(z)}$

С формулой обращения Лагранжа-Бюрмана мы получаем

[z^{n}] E (z) = \frac{1}{n + 1} (\binom{2 n}{n})

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

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

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

введите описание изображения здесь

одинарные бинарные деревья. У них тоже есть производящая функция однако их коэффициент отличается. Вы получаете числа Моцкина

T = {∙} \times {S E Q}_{\leq 2} (T)

$\mathcal{T}=\{\bullet\}\times\mathrm{SEQ}_{\le2}(\mathcal{T})$

T (z) = \frac{1 - z - \sqrt{1 - 2 z - 3 z^{2}}}{2 z}

$T(z)=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}$

[z^{n}] T (z) = \frac{1}{n} \sum_{k} (\binom{n}{k}) (\binom{n - k}{k - 1}) .

$[z^n]T(z)=\frac{1}{n}\sum_k\binom{n}{k}\binom{n-k}{k-1}.$

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

улы
источник

Просто отметим, что «Введение в анализ алгоритмов» Седжвика и Флайолета ( aofa.cs.princeton.edu ) охватывает много того же материала, что и книга «Аналитическая комбинаторика», но в более доступной форме.

vonbrand

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

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

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

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

Реней собственности. Теперь забыть наши последовательности на мгновение и рассмотрят некоторую конечная последовательность целых чисел , , сумма которых составляет 1. Если все непустые префиксы имеют положительные суммы, то нет циклической перестановка этой последовательности имеет то же свойство. Зачем? Хорошо, предположим, что существует такое что также имеет все непустые префиксы положительные. Тогда (свойство последовательности, начинающейся с ) и (свойство последовательности, начинающейся с ); следовательно, $x_1$ $\ldots\,$ $x_m$ $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, которые находятся в биекции с деревьями. Из чисел мы должны выбрать , равный +1, остальные будут -1. Есть способов сделать это. Но только из подсчитанных последовательностей имеет положительные префиксы. Итак, число корневых упорядоченных бинарных деревьев равно: $2n+1$ $n+1$ ${2n+1\choose n+1}$ $1$ $2n+1$

\frac{1}{2 n + 1} (\binom{2 n + 1}{n + 1}) = \frac{1}{2 n + 1} \frac{2 n + 1}{n + 1} (\binom{2 n}{n}) = \frac{1}{n + 1} (\binom{2 n}{n})

${1\over2n+1}{2n+1\choose n+1}={1\over2n+1}{2n+1\over n+1}{2n\choose n}={1\over n+1}{2n\choose n}$

rgrig
источник

Очень хороший ответ, но следующее утверждение требует некоторого объяснения: «учитывая некоторую последовательность с суммой 1, всегда существует циклическая перестановка, которая делает все непустые префиксы положительными»: по крайней мере, намек на доказательство был бы хороший.

Vog

@vog: возьмите префикс с наименьшей суммой и переместите его до конца.

rgrig

@vog: это также должен быть самый длинный префикс, если есть несколько с одинаковой наименьшей суммой. Я отредактировал ответ, чтобы добавить пример в начале.

rgrig