Số lượng cây được gắn nhãn với đồ thị con nhất định sử dụng mã tỉa.

Question

Báo cáo vấn đề

Tôi muốn đếm số cây có đỉnh được đặt $V$ = {1, 2, 3, ..., 10} có $\\$

cây $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (trông giống như 1 - 2 - 3) dưới dạng một đồ thị con.

Vì vậy, nếu tôi nghĩ đúng, tôi cần tìm số cây có nhãn với n đỉnh và 2 cạnh cố định.

Theo công thức của Cayley có $n^{n-2}$ cây có n đỉnh.

Ý của tôi là cây đó -> thuật toán mã tỉa đang tìm lá nhỏ nhất, nối tiếp chuỗi với cha của lá này và loại bỏ lá và cạnh được kết nối với nó. Chúng tôi sẽ có hai vị trí ở trình tự tỉa của chúng tôi bị chiếm bởi (2,2), (3,2), (1, 2). Một trong những chuỗi con này có thể bắt đầu từ$n-1$khe cắm. Các khe khác có thể được sử dụng bởi bất kỳ đỉnh nào trong số n đỉnh. Vì vậy, chúng tôi nhận được$3 \cdot (n-1) \cdot n^{n-4}$. Nhưng nó hoàn toàn sai lầm. Tôi đã cố gắng sử dụng một số bằng chứng về các vấn đề tương tự với một cạnh cố định, nhưng tôi gặp vấn đề với việc hiểu những điều này, dường như ...

Answer 1

Hãy tưởng tượng rằng cây $T$( 3---2---1) được ký hợp đồng với một đỉnh duy nhất có nhãn$0$. Có$8^6$ cây được gắn nhãn trên tập đỉnh $\{0,4,5,6,7,8,9,10\}$. Đối với$k=1,\ldots,7$, có bao nhiêu cây trong số này có đỉnh $0$ có bằng cấp $k$?

Đỉnh $0$ xuất hiện $k-1$ lần trong mã Prüfer của một cây như vậy và mỗi mã Prüfer này có $6$ khe cắm, vì vậy có $\binom6{k-1}$ cách để đặt $k-1$số 0 trong mã. Có sau đó$7$ sự lựa chọn cho từng phần còn lại $6-(k-1)=7-k$ khe cắm, vì vậy hoàn toàn có $\binom6{k-1}7^{7-k}$ những cây như vậy.

Mỗi trong số này tương ứng với nhiều hơn một cây trên tập đỉnh $V$ chứa cái cây $T$. Cụ thể, nếu đỉnh$0$ có bằng cấp $k$ trong một trong những cây này, mỗi cạnh rời khỏi nó có thể được gắn vào bất kỳ trong ba đỉnh $1,2$và $3$ khi chúng ta mở rộng đỉnh $0$ đến $T$, vì vậy cây mở rộng thành $3^k$ các cây khác nhau trên tập hợp đỉnh $V$.

Tổng kết $k=1,\ldots,7$, chúng tôi thấy rằng hoàn toàn có

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

cây trên đỉnh tập hợp $V$ chứa $T$. (Bước áp chót sử dụng định lý nhị thức.)

Phân tích này dễ dàng tổng quát thành công thức cho số lượng cây được gắn nhãn trên $n$ đỉnh chứa một cây con cụ thể $T$ với $m$ các đỉnh.