Numero di alberi etichettati con un dato sottografo utilizzando il codice prufer.

Question

Dichiarazione problema

Voglio contare il numero di alberi con i vertici impostati $V$ = {1, 2, 3, ..., 10} che hanno $\\$

albero $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (sembra 1 - 2 - 3) come sottografo.

Quindi, se penso correttamente, ho bisogno di trovare il numero di alberi etichettati con n vertici e 2 bordi fissi.

Secondo la formula di Cayley ci sono $n^{n-2}$ alberi con n vertici.

La mia opinione è che l'algoritmo del codice albero -> prufer sta trovando la foglia più piccola, aggiungendo una sequenza al genitore di questa foglia e rimuovendo questa foglia e il bordo ad essa collegati. Avremo due slot alla nostra sequenza prufer occupati da (2,2), (3,2), (1, 2). Una di queste sottosequenze può iniziare$n-1$slot. Altri slot possono essere utilizzati da uno qualsiasi di n vertici. Quindi otteniamo$3 \cdot (n-1) \cdot n^{n-4}$. Ma è completamente sbagliato. Ho provato a utilizzare alcune prove di problemi simili con un bordo fisso, ma ho problemi a comprenderli a quanto pare ...

Answer 1

Immagina che l'albero $T$( 3---2---1) è contratto a un singolo vertice etichettato$0$. Ci sono$8^6$ alberi etichettati sul set di vertici $\{0,4,5,6,7,8,9,10\}$. Per$k=1,\ldots,7$, in quanti di questi alberi fa il vertice $0$ avere una laurea $k$?

Vertice $0$ si presenta $k-1$ volte nel codice Prüfer di un tale albero, e ciascuno di questi codici Prüfer ha $6$ slot, quindi ci sono $\binom6{k-1}$ modi per posizionare il file $k-1$zeri nel codice. Ci sono poi$7$ scelte per ciascuno dei restanti $6-(k-1)=7-k$ slot, quindi ci sono del tutto $\binom6{k-1}7^{7-k}$ tali alberi.

Ognuno di questi corrisponde a più di un albero sull'insieme dei vertici $V$ che contiene l'albero $T$. In particolare, se vertice$0$ ha una laurea $k$ in uno di questi alberi, ciascuno dei bordi che lo lasciano può essere attaccato a uno qualsiasi dei tre vertici $1,2$, e $3$ quando espandiamo vertice $0$ per $T$, quindi l'albero si espande in $3^k$ diversi alberi sul vertice impostato $V$.

Riassumendo $k=1,\ldots,7$, scopriamo che ci sono del tutto

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

alberi sul vertice impostato $V$ che contengono $T$. (Il penultimo passaggio utilizza il teorema binomiale.)

Questa analisi si generalizza facilmente a una formula per il numero di alberi etichettati $n$ vertici che contengono una sottostruttura specifica $T$ con $m$ vertici.