Ön kod kullanılarak verilen alt grafiğe sahip etiketli ağaçların sayısı.

Aug 17 2020

Sorun bildirimi

Köşe seti olan ağaçların sayısını saymak istiyorum $V$ = {1, 2, 3, ..., 10} olan $\\$

ağaç $T=$ Alt grafik olarak <{1, 2, 3}, {{1, 2}, {2, 3}}> (1 - 2 - 3'e benzer).

Yani doğru düşünürsem, n köşeli ve 2 sabit kenarlı etiketli ağaçların sayısını bulmam gerekiyor.

Cayley'in formülüne göre $n^{n-2}$ n köşeli ağaçlar.

Benim fikrime göre ağaç -> prufer kod algoritması en küçük yaprağı buluyor, bu yaprağın ebeveynine sıra ekliyor ve bu yaprağı ve ona bağlı kenarı kaldırıyor. Ön dizimizde (2,2), (3,2), (1, 2) tarafından işgal edilen iki yuvaya sahip olacağız. Bu alt dizilerden biri şu tarihte başlayabilir:$n-1$yuvalar. Diğer yuvalar n köşeden herhangi biri tarafından kullanılabilir. Böylece anlıyoruz$3 \cdot (n-1) \cdot n^{n-4}$. Ama bu tamamen yanlış. Benzer sorunların bazı kanıtlarını tek bir sabit uçla kullanmayı denedim, ancak bunları anlamakta sorun yaşıyorum, öyle görünüyor ki ...

Yanıtlar

1 BrianM.Scott Aug 17 2020 at 08:17

Ağacın $T$( 3---2---1) etiketli tek bir köşe ile sözleşmeli$0$. Var$8^6$ köşe kümesindeki etiketli ağaçlar $\{0,4,5,6,7,8,9,10\}$. İçin$k=1,\ldots,7$, bu ağaçların kaçında tepe noktası var $0$ derecesi var $k$?

Tepe noktası $0$ ortaya çıkıyor $k-1$ Bu tür bir ağacın Prüfer kodundaki zamanlar ve bu Prüfer kodlarının her biri $6$ yuvalar, yani var $\binom6{k-1}$ yerleştirmenin yolları $k-1$kodda sıfırlar. O zaman var$7$ kalan her biri için seçenekler $6-(k-1)=7-k$ yuvalar, yani tamamen var $\binom6{k-1}7^{7-k}$ böyle ağaçlar.

Bunların her biri, köşe kümesindeki birden fazla ağaca karşılık gelir $V$ ağacı içeren $T$. Özellikle, köşe$0$ derecesi var $k$ bu ağaçlardan birinde, onu terk eden kenarların her biri, üç köşeden herhangi birine bağlanabilir $1,2$, ve $3$ tepe noktasını genişlettiğimizde $0$ -e $T$, böylece ağaç genişler $3^k$ köşe kümesindeki farklı ağaçlar $V$.

Özetle $k=1,\ldots,7$, hep birlikte olduğunu görüyoruz

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

köşe kümesindeki ağaçlar $V$ içeren $T$. (Sondan bir önceki adım, iki terimli teoremi kullanır.)

Bu analiz, üzerindeki etiketli ağaçların sayısı için bir formüle kolayca genelleştirir. $n$ belirli bir alt ağaç içeren köşeler $T$ ile $m$ köşeler.