프 루퍼 코드를 사용하여 지정된 하위 그래프가있는 레이블이 지정된 트리 수.

Aug 17 2020

문제 설명

정점 세트로 나무 수를 세고 싶습니다. $V$ = {1, 2, 3, ..., 10} $\\$

나무 $T=$ <{1, 2, 3}, {{1, 2}, {2, 3}}> (1-2-3과 유사) 하위 그래프로.

따라서 올바르게 생각하면 n 개의 꼭지점과 2 개의 고정 된 가장자리를 가진 레이블이 지정된 나무의 수를 찾아야합니다.

Cayley의 공식에 따르면 $n^{n-2}$ n 개의 꼭지점이있는 나무.

내 생각은 트리-> prufer 코드 알고리즘이 가장 작은 잎을 찾고이 잎의 부모와 함께 시퀀스를 추가 하고이 잎과 가장자리를 제거하는 것입니다. (2,2), (3,2), (1, 2)가 차지하는 prufer 시퀀스에 두 개의 슬롯이 있습니다. 이러한 하위 시퀀스 중 하나는$n-1$슬롯. n 개의 정점 중 하나에서 다른 슬롯을 사용할 수 있습니다. 그래서 우리는$3 \cdot (n-1) \cdot n^{n-4}$. 그러나 그것은 완전히 잘못되었습니다. 나는 하나의 고정 된 가장자리로 비슷한 문제에 대한 몇 가지 증명을 사용하려고했지만 이것들을 이해하는 데 문제가 있습니다 ...

답변

1 BrianM.Scott Aug 17 2020 at 08:17

나무가 $T$( 3---2---1)는 레이블이 지정된 단일 정점으로 축소됩니다.$0$. 있습니다$8^6$ 정점 세트의 레이블이 지정된 나무 $\{0,4,5,6,7,8,9,10\}$. 에 대한$k=1,\ldots,7$, 얼마나 많은 나무가 정점을 수행하는지 $0$ 학위가있다 $k$?

꼭지점 $0$ 나타나다 $k-1$ 이러한 트리의 Prüfer 코드에있는 시간, 그리고 이러한 Prüfer 코드 각각은 $6$ 슬롯, 그래서 있습니다 $\binom6{k-1}$ 배치하는 방법 $k-1$코드에서 0입니다. 그런 다음$7$ 나머지 각각에 대한 선택 $6-(k-1)=7-k$ 슬롯, 그래서 모두 있습니다 $\binom6{k-1}7^{7-k}$ 그런 나무.

이들 각각은 정점 세트에있는 둘 이상의 트리에 해당합니다. $V$ 나무를 포함하는 $T$. 특히 정점이$0$ 학위가있다 $k$ 이 나무 중 하나에서 떠나는 각 가장자리는 세 개의 정점 중 하나에 연결될 수 있습니다. $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$. (두 번째 단계는 이항 정리를 사용합니다.)

이 분석은 레이블이 지정된 트리 수에 대한 공식으로 쉽게 일반화됩니다. $n$ 특정 하위 트리를 포함하는 정점 $T$$m$ 정점.