Skip to main content

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Yhttp://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

link corrected
Source Link
esg
  • 3.3k
  • 11
  • 15

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199607)8:4http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://www.dx.doi.org/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$

Source Link
esg
  • 3.3k
  • 11
  • 15

The asymptotic distribution of the number of nodes at maximal height in a random tree is known.

The following was known as "Wilf's conjecture" (H. S. Wilf stated it in 1991, evidently unaware of the fact that it had been popularized among Russian combinatorialists by V. F. Kolchin earlier):

Choose a labeled tree of $n$ vertices uniformly among all $n^{n-2}$ labeled trees and let $L_n$ be the number of vertices at maximal graph distance from its root (the vertex with label $1$).
Then $L_n$ converges in distribution as $n\rightarrow \infty$, i.e., there exists a probability distribution $(q_\ell)_{\ell\geq 1}$ such that $$\mathbb{P}(L_n=\ell)\longrightarrow q_\ell,\;\;\ell\ge 1$$

This conjecture was settled by Kesten and Pittel in 1996, see http://onlinelibrary.wiley.com/doi/10.1002/(SICI)1098-2418(199607)8:4<243::AID-RSA1>3.0.CO;2-Y

Kesten and Pittel proved (Corollary 2, page 8) that the conjecture is true, and that $$q_\ell=\pi_\ell e^{-\ell}$$ where $(\pi_\ell)_{\ell\geq 1}$ is the unique solution of $$\pi_\ell\geq 0,\;\;\;\;\pi_\ell=\sum_{k=1}^\infty \pi_k\,e^{-k}\frac{k^\ell}{\ell!},\;\;\;\,\sum_{\ell=1}^\infty \pi_{\ell}e^{-\ell} =1$$