랜덤 노드가 리프 노드 일 확률
한계를 어떻게 보여줄 수 있습니까? $n$ 구혼 $\infty$, 다음을 포함하는 트리의 주어진 노드에 대한 확률 $n$ 정점 및 $n - 1$ 잎 노드가 접근하는 가장자리 $1/e$?
제 생각에이 문제는 올바른 접근 방식을 취하려는 것입니다. 나는 한계를 적 으려고 노력했습니다.$n$ 그리고 사실을 사용하여 $\lim_{n\to \infty} (1 - 1/n)^{n} = e^{-1},$ 하지만 확률을 적을 수는 없습니다.
나는 나무에 대한 확률을 $n$ 트리에 대한 노드 $n - 1$노드 (반복 관계)이지만 그렇게 할 수 없었습니다. 나는 또한 학위를 가진 정점의 수에 대한 관계를 생각해 보았습니다.$1$ Handshaking Lemma를 사용했지만 이것은 나를 아무데도 가져 가지 않았습니다.
도움을 주시면 감사하겠습니다
답변
한계 값보기 $1/e$, 여기에서 레이블이 지정된 트리 에 대해 이야기하고 있다고 생각합니다 (OP는이 점을 명확히해야합니다!).
고전적인 Cayley의 공식 을 일반화함으로써 $n^{n-2}$ 나무의 수를 제공합니다. $n$ 레이블이 지정된 정점, 생성 함수를 얻습니다. $$(x_1+x_2+\dots+x_n)^{n-2}=\sum \prod_{k=1}^n x_k^{d_T(v_k)-1}$$ 여기서 오른쪽에서 각 단항식은 나무를 나타냅니다. $T$ 와 $n$ 레이블이있는 정점 $v_k$ 학위가있는 각각 $d_T(v_k)$. 자, 주어진 노드는$v_n$, 그 정도가 다음과 같은 경우에만 잎입니다. $1$, 그건 $d_T(v_n)-1=0$. 따라서 총 나무 수는$n$ 레이블이 지정된 정점 $v_n$ 잎은 시켜서 얻을 수 있습니다 $x_n=0$, 그리고 나머지 $x_k=1$ 위의 공식에서 $(n-1)^{n-2}$.
따라서 나무에 대한 원하는 확률은 $n$ 레이블이 지정된 노드는 $$p_n=\frac{(n-1)^{n-2}}{n^{n-2}}=\left(1-\frac{1}{n}\right)^{n-2}\to \frac{1}{e}\quad \text{as $n \ to \ infty$.}$$
예. 에 대한$n=4$ 우리는 $4^2=16$ 라벨이 붙은 나무와 $$p_4=\frac{\text{number of trees with a blue leaf}}{16}=\frac{9}{16}.$$
