プリューファーコードを使用して、指定されたサブグラフを持つラベル付きツリーの数。
問題文
頂点が設定された木の数を数えたい $V$ = {1、2、3、...、10} $\\$
木 $T=$ <{1、2、3}、{{1、2}、{2、3}}>（1 --2 --3のように見えます）をサブグラフとして。
したがって、正しく考えると、n個の頂点と2個の固定エッジを持つラベル付きツリーの数を見つける必要があります。
ケイリーの公式によると、 $n^{n-2}$ n個の頂点を持つツリー。
私の見解は、ツリー->プリューファーコードアルゴリズムが最小の葉を見つけ、この葉の親でシーケンスを追加し、この葉とそれに接続されているエッジを削除することです。プリューファー列には、（2,2）、（3,2）、（1、2）のいずれかが占める2つのスロットがあります。これらのサブシーケンスの1つは$n-1$スロット。他のスロットは、n個の頂点のいずれかで使用できます。だから私たちは得る$3 \cdot (n-1) \cdot n^{n-4}$。しかし、それは完全に間違っています。1つの固定エッジで同様の問題の証明のいくつかを使用しようとしましたが、これらを理解するのに問題があるようです...
回答
その木を想像してみてください $T$（3---2---1）は、ラベルが付けられた単一の頂点に縮小されます$0$。がある$8^6$ 頂点セット上のラベル付きツリー $\{0,4,5,6,7,8,9,10\}$。にとって$k=1,\ldots,7$、これらの木の数で頂点を実行します $0$ 学位を持っている $k$？
バーテックス $0$ 現れます $k-1$ そのような木のプリューファーコードの時間、そしてこれらのプリューファーコードのそれぞれは持っています $6$ スロットがあるので $\binom6{k-1}$ 配置する方法 $k-1$コード内のゼロ。それからあります$7$ 残りのそれぞれの選択肢 $6-(k-1)=7-k$ スロットなので、全部あります $\binom6{k-1}7^{7-k}$ そのような木。
これらのそれぞれは、頂点セット上の複数のツリーに対応します $V$ 木が含まれています $T$。具体的には、頂点の場合$0$ 学位を持っている $k$ これらの木の1つでは、それを離れる各エッジを3つの頂点のいずれかにアタッチできます。 $1,2$、および $3$ 頂点を展開するとき $0$ に $T$、したがって、ツリーはに展開されます $3^k$ 頂点セット上のさまざまなツリー $V$。
まとめる $k=1,\ldots,7$、私たちは完全にあることがわかります
$$\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*}$$
頂点セットの木 $V$ 含まれている $T$。（最後から2番目のステップは二項定理を使用します。）
この分析は、上のラベル付きツリーの数の式に簡単に一般化されます。 $n$ 特定のサブツリーを含む頂点 $T$ と $m$ 頂点。