Contando árvores binárias

28

(Eu sou um estudante com alguma formação matemática e gostaria de saber como contar o número de um tipo específico de árvores binárias.)

Olhando a página da Wikipedia para Árvores binárias , observei esta afirmação de que o número de árvores binárias enraizadas de tamanho $n$ seria este número catalão :

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

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

Mas eu não entendo como eu poderia chegar a esse resultado sozinho. Existe um método para encontrar esse resultado?

Agora, e se a ordem das subárvores (que é deixada, que é certa) não for considerada? Por exemplo, do meu ponto de vista, considero que essas duas árvores são iguais:

   /\   /\
  /\     /\

Seria possível aplicar um método semelhante para contar quantos desses objetos possuem exatamente nós? $n$

combinatorics binary-trees discrete-mathematics Stéphane Gimenez
fonte

O teorema da contagem de Polya em árvores com 2 aros enraizadas é aplicável aqui?

Nicholas Mancuso 14/03

35

Para contar muitos tipos de objetos combinatórios, como árvores neste caso, existem ferramentas matemáticas poderosas (o método simbólico) que permitem derivar mecanicamente essas contagens de uma descrição de como os objetos combinatórios são construídos. Isso envolve gerar funções.

Uma excelente referência é a Analytic Combinatorics , do falecido Philipe Flajolet e Robert Sedgewick. Está disponível no link acima.

O livro do falecido Herbert Wilf, que gera a funcionalidade, é outra fonte livre.

E, é claro, a Matemática Concreta da GKP é um tesouro.

Para árvores binárias, é assim: primeiro você precisa de uma definição clara da árvore.

Uma árvore binária é uma árvore enraizada na qual todo nó não-folha possui exatamente o grau 2.

Em seguida, temos que concordar com o que queremos chamar de tamanho de uma árvore.

insira a descrição da imagem aqui

À esquerda, todos os nós são iguais. No meio, distinguimos as folhas e as não-folhas. À direita, temos uma árvore binária podada, onde as folhas foram removidas. Observe que ele tem ramificações unárias de dois tipos (esquerda e direita)!

Agora temos que derivar uma descrição de como esses objetos combinatórios são construídos. No caso de árvores binárias, é possível uma decomposição recursiva .

Seja o conjunto de todas as árvores binárias do primeiro tipo e, simbolicamente, temos: $\mathcal{A}$ insira a descrição da imagem aqui

Ele lê como: “Um objeto da classe de árvores binárias é um nó ou um nó seguido por duas árvores binárias.” Isso pode ser escrito como equação de conjuntos:

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

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

Ao introduzir a função geradora que enumera essa classe de objetos combinatórios, podemos converter a equação definida em uma equação envolvendo a função geradora. $A(z)$

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

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

Nossa escolha de tratar todos os nós igualmente e considerar o número de nós na árvore como noção de seu tamanho é expressa pela “marcação” dos nós com a variável . $z$

Agora podemos resolver a equação quadrática para e obter, como sempre, duas soluções, a forma fechada explícita da função geradora: $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}$

Agora, simplesmente precisamos do Teorema Binomial de Newton (generalizado):

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

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

com e para expandir a forma fechada da função volta gerador em uma série de potências. Fazemos isso porque, o coeficiente em é apenas o número de objetos combinatórios de tamanho , normalmente escritos como . Mas aqui nossa noção do "tamanho" da árvore nos obriga a procurar o coeficiente em . Após um pouco de malabarismo com binômios e fatoriais, obtemos: $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}.$

Se começarmos com a segunda noção do tamanho, a decomposição recursiva é:

insira a descrição da imagem aqui

Temos uma classe diferente de objetos combinatórios . Diz: "Um objeto da classe de árvores binárias é uma folha ou um nó interal seguido por duas árvores binárias". $\mathcal{B}$

Podemos usar a mesma abordagem e transformar em . Só que desta vez a variável marca apenas os nós internos, não as folhas, porque a definição "o tamanho" é diferente aqui. Também temos uma função geradora diferente: $\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}$

Extraindo os rendimentos do coeficiente

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

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

As classes e concordam com as contagens, porque uma árvore binária com nós internos possui folhas, portanto, nós no total. $\mathcal{A}$ $\mathcal{B}$ $n$ $n+1$ $2n+1$

No último caso, temos que trabalhar um pouco mais:

insira a descrição da imagem aqui

que é uma descrição de tentativas binárias removidas não vazias. Estendemos isso para

\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}$

e reescrevê-lo com funções de geração

\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}$

resolver as equações quadráticas

\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}$

e volte mais uma vez

[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$

Observe que a função geradora catalã é

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

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

enumera a classe de árvores gerais . Essas são as árvores sem restrição no grau do nó.

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

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

Ele lê como: "Um objeto da classe de árvores gerais é um nó seguido por uma possível sequência vazia de árvores gerais".

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

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

Com a Fórmula de Inversão Lagrange-Bürmann obtemos

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

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

Então, provamos que existem tantas árvores em geral quanto árvores binárias. Não é de admirar que exista uma bijeção entre as árvores gerais e as binárias. A bijeção é conhecida como correspondência de rotação (explicada no final do artigo vinculado), que nos permite armazenar duas árvores gerais como uma árvore binária.

Observe que, se não distinguirmos os irmãos esquerdo e direito na classe , obteremos mais uma classe de árvores : $\mathcal{C}$ $\mathcal{T}$

insira a descrição da imagem aqui

as árvores binárias unárias. Eles também têm uma função geradora no entanto, seu coeficiente é diferente. Você obtém os números de Motzkin

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}.$

Ah, e se você não gosta de gerar funções, há muitas outras provas também. Veja aqui , existe um em que você pode usar a codificação de árvores binárias como palavras Dyck e derivar uma recorrência de sua definição recursiva. Resolver essa recorrência também dá a resposta. No entanto, o método simbólico evita que você aconteça com a recorrência em primeiro lugar, pois trabalha diretamente com os projetos dos objetos combinatórios.

uli
fonte

Apenas para observar que "Introdução à análise de algoritmos" de Sedgewick e Flajolet ( aofa.cs.princeton.edu ) cobre muito do mesmo material que o livro "Analítica Combinatória", mas de uma forma mais acessível.

vonbrand

7

As funções geradoras são uma varinha mágica muito poderosa e muito útil. A solução a seguir para a primeira pergunta (por que existem árvores ) é um pouco menos mágica. Por isso, fofo. $C_n$

Exemplo. Para produzir uma árvore de nós, começamos com uma sequência na qual ocorre vezes e ocorre vezes. Por exemplo, . Entre os prefixos com a menor soma (e possivelmente negativa), escolha a mais longa; neste caso, . Pegue esse prefixo desde o início e coloque-o no final; neste caso, obtemos . Agora mude para e para ; neste caso, chegamos . Remova um do começo, adicione um $5$ $+1$ $5+1$ $-1$ $5$ $+-++-+--++-$ $+-++-+--$ $++-+-++-+--$ $+$ $T$ $-$ $E$ TTETETTETEE $T$ $E$ no fim; neste caso, chegamos TETETTETEEE. Esta é uma descrição da árvore T(E,T(E,T(T(E,T(E,E)),E))). Abaixo há uma explicação de por que isso é uma bijeção. Uma vez convencido disso, a contagem é fácil. Existem seqüências de , então dividimos por porque escolhemos uma das possíveis permutações cíclicas. $\binom{5+6}{5}$ $\pm1$ $5+6$

Primeira bijeção. Uma definição típica para árvores em ML é type tree = T of tree * tree | E; isto é, uma árvore possui duas subárvores (ordenadas) ou está vazia. Aqui está como árvores são construídos: T(T(E,E),T(T(E,E),T(E,E))). Soltando cotão, podemos simplesmente escrever TTEETTEETEE. Todas essas descrições vai acabar com um E, por isso é redundante: TTEETTEETE. (Observe que a árvore vazia agora corresponde à cadeia vazia.) Essas cadeias possuem a propriedade de que cada prefixo possui pelo menos tantos Ts quanto Es e, no total, possuem Ts e Es, em que é o número de nós de a árvore. $n$ $n$ $n$

Segunda bijeção. Agora substituímos T por +1 e E por -1. Então, estamos vendo sequências com valores +1, com valores -1 e com as somas de todos os prefixos . $n$ $n$ $\ge0$

Terceira bijeção. Agora, alteramos um pouco o requisito de prefixos: pedimos que a soma de cada prefixo não vazio seja . Para que isso seja possível, deixamos valores +1 valores -1. (Caso contrário, a soma de toda a cadeia seria 0 e falharia em atender à condição dos prefixos.) Essas seqüências devem começar com +1. Então, eles realmente são os mesmos de antes, exceto que eles têm um +1 preso no começo. $>0$ $n+1$ $n$

Propriedade Raney. Agora esquecer os nossos seqüências por um momento e considerar alguns sequência finita de números inteiros , , cuja soma é 1. Se todos os prefixos não vazios têm somas positivas, então permutação não cíclica desta seqüência tem a mesma propriedade. Por quê? Bem, suponha que exista um tal que também tenham todos os prefixos não vazios positivos. Então (propriedade da sequência iniciada em ) e (propriedade da sequência iniciada em ); portanto, $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$ , o que contradiz a suposição de que a soma para toda a sequência é 1.

Além disso, dada uma sequência com a soma 1, sempre existe uma permutação cíclica que faz com que todos os prefixos não vazios tenham soma positiva. (Isso é verdade mesmo para números reais.)

Conclusão. Agora vamos contar as sequências de +1 e -1 que estão em uma bijeção com árvores. Fora de números, devemos escolher que seja igual a +1, os outros serão -1. Existem maneiras de fazer isso. Porém, apenas em seqüências contadas até o momento possui prefixos positivos. Portanto, o número de árvores binárias enraizadas e ordenadas é: $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
fonte

Resposta muito boa, mas a seguinte declaração precisa de alguma explicação: "dada uma sequência com a soma 1, sempre há uma permutação cíclica que faz com que todos os prefixos não vazios tenham soma positiva" ... ... pelo menos uma dica para a prova seria legais.

vog

11

@ vog: pegue o prefixo com a menor soma e mova-o para o final.

Rgrig 01/05/19

11

@ vog: também deve ser o prefixo mais longo, caso existam múltiplos com a mesma menor soma. Editei a resposta para adicionar um exemplo no começo.

Rgrig 01/05

Contando árvores binárias

Respostas: