= Uniform labelled tree generation
{title2=$\mathbb P(T=t)=n^{-(n-2)}$}
For $n\geq2$, choose $n-2$ <independent random variables>, each with the <uniform distribution on a finite set> $\{1,\ldots,n\}$, and decode their values as a <Prüfer sequence>. Every <sequence> has <probability> $n^{-(n-2)}$, and the <bijection> gives each <labelled tree> the same <probability>. This produces a <uniform spanning tree> of the <complete graph> without repeatedly proposing sets of <edges> and rejecting those that fail to be <trees>. It supplies random inputs for testing implementations of <breadth-first search> and a tractable model of random connections. https://sites.math.rutgers.edu/~zeilberg/Combo20/hw.html[Doron Zeilberger, Rutgers Math 454 (2020), Lecture 23: generate random labelled trees by sampling and inverting Prüfer codes]{ref}
This distribution is uniform over fixed-label <trees>, rather than over <unlabelled trees>. With four labels, the <star graph> shape has <probability> $4/16=1/4$ and the <path graph> shape has <probability> $12/16=3/4$. Also, for a fixed label $v$, the <Prüfer degree formula> gives
$$
\deg_T(v)-1\sim\operatorname{Binomial}(n-2,1/n),
\qquad
\mathbb E[\deg_T(v)]=1+\frac{n-2}{n}=2-\frac2n.
$$
Here the <binomial distribution> counts the <independent> code positions equal to $v$. The <expected value> agrees with the average <vertex degree> from the <degree-sum formula>. Individual labels have the same distribution by symmetry, though their <vertex degrees> are constrained together by their fixed sum. When $n=1$, simply return the single isolated <vertex>.
Back to article page
