My question is about a sentence in the proof of the following proposition:

Proposition 2.3. The uniform random tree $\mathbb{T}_{n}$ has the same distribution as a tree generated as follows:

  • Take a Galton-Watson tree with Poisson(1) offspring distribution;
  • Condition it to have total progeny precisely (n);
  • Assign the vertices random labels chosen from [n] and forget the original ordering.

Proof. Recall the standard labelling of the vertices of a Galton-Watson tree $\mathbf{T}$, and let $\mathbf{t}$ be a particular tree with $\#(\mathbf{t})=n$ and numbers of offspring $c\left(v_{1}\right)=c_{1}, \ldots, c\left(v_{n}\right)=c_{n}$. Then $$ \mathbb{P}(\mathbf{T}=\mathbf{t})=\prod_{i=1}^{n} \frac{e^{-1}}{c_{i} !}=e^{-n} \prod_{i=1}^{n} \frac{1}{c_{i} !} $$ Now observe that $\mathbb{P}(\#(\mathbf{T})=n)$ is a function only of $n$. Hence, $$ \mathbb{P}(\mathbf{T}=\mathbf{t} \mid \#(\mathbf{T})=n)=f(n) \prod_{i=1}^{n} \frac{1}{c_{i} !} $$ for some function $f$. Now consider labelling the vertices of $\mathbf{T}$ with $[n]:=\{1,2, \ldots, n\}$. There are $n!$ different ways to do this, of which $\prod_{i=1}^{n} c_{i} !$ give rise to the same unordered labelled tree, once we forget the ordering. Hence, the probability of obtaining a particular labelled unordered tree $t$ is $f(n) / n !$. Since this depends only on $n$, and not on any other feature of the tree, it must be the case that the tree is uniformly distributed on $\mathbb{T}_{n}$.

(From An introduction to random trees by Christina Goldschmidt )

There is one part I do not understand, why do $\prod_{i=1}^{n} c_{i} !$ out of the $n!$ different ways give rise to the same unordered labelled tree?


1 Answer 1


Permuting the offspring of any subset of the vertices does not change the unlabelled tree, because it preserves all of the parent-child relationships that define the tree. For each $k\in[n]$ there are $c_k!$ ways to permute the offspring of $v_k$, so there are altogether $\prod_{k=1}^nc_k!$ ways to permute the offspring of each vertex: you can combine any of the $c_1!$ permutations of the offspring of $v_1$ with any of the $c_2!$ permutations of the offspring of $v_2$ and so on without changing the underlying unlabelled tree.

Or you can turn it around. Suppose that $T$ is an unlabelled (rooted) tree on $n$ vertices. In the standard labelling the root must be labelled $\varnothing$. If it has $c_1$ offspring, they can then be labelled $1,2,\ldots,c_1$ in any of $c_1!$ orders. If the vertex now labelled $1$ has $c_2$ offspring, these can be labelled $11,12,\ldots,1c_2$ in any of $c_2!$ different orders. Continuing in this fashion, it the numbers of offspring of the $n$ vertices are $c_1,\ldots,c_k$, we have $\prod_{k=1}^nc_k!$ different ways to label the vertices using the standard labelling, depending on how we order the offspring of each vertex.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .