Número de árvores rotuladas com determinado subgrafo usando código prufer.

Question

Declaração do problema

Eu quero contar o número de árvores com conjunto de vértices $V$ = {1, 2, 3, ..., 10} que tem $\\$

árvore $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (parece 1 - 2 - 3) como um subgráfico.

Então, se eu pensar corretamente, preciso encontrar o número de árvores rotuladas com n vértices e 2 arestas fixas.

Pela fórmula de Cayley, existem $n^{n-2}$ árvores com n vértices.

Minha opinião é que o algoritmo de código árvore -> prufer está encontrando a menor folha, anexando sequência com o pai desta folha e removendo esta folha e a borda conectada a ela. Teremos dois slots em nossa seqüência de prufer ocupados por (2,2), (3,2), (1, 2). Uma dessas subsequências pode começar em$n-1$slots. Outros slots podem ser usados ​​por qualquer um dos n vértices. Então nós temos$3 \cdot (n-1) \cdot n^{n-4}$. Mas está completamente errado. Tentei usar algumas das provas de problemas semelhantes com uma aresta fixa, mas parece que tenho problemas em compreender estas ...

Answer 1

Imagine que a árvore $T$( 3---2---1) é contraído a um único vértice rotulado$0$. tem$8^6$ árvores rotuladas no conjunto de vértices $\{0,4,5,6,7,8,9,10\}$. Para$k=1,\ldots,7$, em quantas dessas árvores o vértice $0$ tem diploma $k$?

Vértice $0$ Aparece $k-1$ vezes no código Prüfer de tal árvore, e cada um desses códigos Prüfer tem $6$ slots, então há $\binom6{k-1}$ maneiras de colocar o $k-1$zeros no código. Então existem$7$ escolhas para cada um dos restantes $6-(k-1)=7-k$ slots, então existem $\binom6{k-1}7^{7-k}$ tais árvores.

Cada um deles corresponde a mais de uma árvore no conjunto de vértices $V$ que contém a árvore $T$. Especificamente, se o vértice$0$ tem diploma $k$ em uma dessas árvores, cada uma das arestas que sai pode ser anexada a qualquer um dos três vértices $1,2$e $3$ quando expandimos vértice $0$ para $T$, então a árvore se expande para $3^k$ árvores diferentes no conjunto de vértices $V$.

Resumindo $k=1,\ldots,7$, descobrimos que existem

$$\begin{align*} \sum_{k=1}^73^k\binom6{k-1}7^{7-k}&=\sum_{k=0}^6\binom6k3^{k+1}7^{6-k}\\ &=3\sum_{k=0}^6\binom6k3^k7^{6-k}\\ &=3(3+7)^6\\ &=3,000,000 \end{align*}$$

árvores no conjunto de vértices $V$ que contém $T$. (A penúltima etapa usa o teorema binomial.)

Esta análise se generaliza facilmente para uma fórmula para o número de árvores rotuladas em $n$ vértices que contêm uma subárvore específica $T$ com $m$ vértices.