# Why this two model have same probability distribution?

(1)

Consider the following method of generating a random tree with $n$ nodes.

First expand the root node into two branches.

Then expand one of the two terminal nodes at random.

At time $k$, choose one of the $k - 1$ terminal nodes according to a uniform distribution and expand it. Continue until $n$ terminal nodes have been generated.

(2)

Consider another generating method.

First choose an integer $N_1$ uniformly distributed on {$1,2,...,n-1$}. Then we expand the root node into to branches with $N_1$ and $n-N_1$ writing under them.

Then do the same thing recursively until some node become 2 and expand into 1 and 1.

I was told such to generating method will yield the same probability distribution. The hint say to use a Polya's urn model to explain it. But I'm confused.

Anyone can explain it to me?

-
Looks like homework. Is it? – Brendan McKay Aug 18 '12 at 7:29
It is from the exercises in a Information Theory book. I'm studying it by myself. – user18717 Aug 18 '12 at 9:52
More specific hint: what is the distribution of the number of nodes in the left side of the tree under both distributions? – Ori Gurel-Gurevich Aug 18 '12 at 16:48
I got it! Thank you, Ori! – user18717 Aug 19 '12 at 5:51