Nombre d'arbres étiquetés avec un sous-graphe donné utilisant le code prufer.

Question

Énoncé du problème

Je veux compter le nombre d'arbres avec un ensemble de sommets $V$ = {1, 2, 3, ..., 10} qui ont $\\$

arbre $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (ressemble à 1 - 2 - 3) en tant que sous-graphe.

Donc, si je pense correctement, je dois trouver le nombre d'arbres étiquetés avec n sommets et 2 arêtes fixes.

Selon la formule de Cayley, il y a $n^{n-2}$ arbres à n sommets.

Mon opinion est que l'algorithme de code tree -> prufer trouve la plus petite feuille, ajoute la séquence avec le parent de cette feuille et supprime cette feuille et le bord qui lui sont connectés. Nous aurons deux emplacements à notre séquence préférée occupés par (2,2), (3,2), (1, 2). L'une de ces sous-séquences peut démarrer sur$n-1$slots. D'autres emplacements peuvent être utilisés par n'importe lequel des n sommets. Alors on obtient$3 \cdot (n-1) \cdot n^{n-4}$. Mais c'est complètement faux. J'ai essayé d'utiliser certaines preuves de problèmes similaires avec un bord fixe, mais j'ai du mal à les comprendre, il semble ...

Answer 1

Imaginez que l'arbre $T$( 3---2---1) est contracté à un seul sommet étiqueté$0$. Il y a$8^6$ arbres étiquetés sur l'ensemble de sommets $\{0,4,5,6,7,8,9,10\}$. Pour$k=1,\ldots,7$, dans combien de ces arbres le sommet $0$ avoir un diplôme $k$?

Sommet $0$ révéler $k-1$ fois dans le code Prüfer d'un tel arbre, et chacun de ces codes Prüfer a $6$ slots, donc il y a $\binom6{k-1}$ façons de placer le $k-1$des zéros dans le code. Il y a alors$7$ choix pour chacun des autres $6-(k-1)=7-k$ slots, donc il y a tout à fait $\binom6{k-1}7^{7-k}$ ces arbres.

Chacun d'eux correspond à plus d'un arbre sur l'ensemble de sommets $V$ qui contient l'arbre $T$. Plus précisément, si sommet$0$ a un diplôme $k$ dans l'un de ces arbres, chacune des arêtes la laissant peut être attachée à l'un des trois sommets $1,2$, et $3$ lorsque nous développons un sommet $0$ à $T$, ainsi l'arborescence se développe en $3^k$ différents arbres sur l'ensemble de sommets $V$.

En résumé $k=1,\ldots,7$, nous constatons qu'il y a au total

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

arbres sur l'ensemble de sommets $V$ qui contiennent $T$. (L'avant-dernière étape utilise le théorème binomial.)

Cette analyse se généralise facilement à une formule pour le nombre d'arbres étiquetés sur $n$ sommets contenant un sous-arbre spécifique $T$ avec $m$ sommets.