(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?