# Probability of a particular randomly generated tree shape?

I start with a one-node tree. Then I repeatedly choose a node uniformly at random and add a child node to it, stopping when there are a certain number of nodes.

Treating all nodes as equivalent and ignoring the order of children of a node, I'd like to calculate the probabiity of producing a given shape of tree.

For example, there is only 1 way to produce the 1 or 2 node tree, so each of those are 100% likely if I stop at 1 or 2 nodes. If I'm producing a 3-node tree then I might get A->B->C or C<-A->B, each with 50% probability depending on which of A or B was chosen before adding C. From either of those trees, D could get inserted in one of three places (as a child of A, B, or C), but some of those results are equivalent:

1. A->B->C
->D

2. A->B->C
->D

3. A->B->C->D

4. A->B
|->C
->D

5. A->B->D
->C

6. A->B
->C->D


1, 5, and 6 are all the same tree structure, so there's a 50% chance of producing that tree, and a 16.67% chance of producing each of the other three (2, 3, 4).

• Does the order in which the node are added matter? I mean: are D<-B<-A->C and C<-B<-A->D the same shape? – wece Jun 8 '15 at 10:17
• No. The nodes are indistinct once they are added. I've only lettered them for convenience of describing the process. – Sparr Jun 8 '15 at 13:32
• Is it a binary tree? – Tianyu Zheng Jun 8 '15 at 13:49
• @TianyuZheng no. As described, the parent for each new child is chosen at random from all previous nodes. – Sparr Jun 8 '15 at 13:52

There are $(k-1)!$ possible trees with $k$ nodes generated by your algorithm. We now compute, given a shape $T=(N,E)$, the number of trees generated by your algorithm of shape $T$.

First some notations: given an edge $e=(n_1,n_2)\in E$ we denote $\#(e)$ the number of edges in the sub-tree with root $n_2$ plus one.

We define inductively $g(n)$ the number of way to generate the sub-tree of root $n$.

• If $n$ is a leaf then $g(n)=1$.
• If there is only one edge $e=(n,n_1)\in E$ out of $n$ then $g(n)=g(n_1)$
• Otherwise let $e_1=(n,n_1);\dots;e_l=(n,n_l)$ be the set of all edges going out of $n$. $$g(n)=\prod_{i=1}^{l-1}{\sum_{j=1}^{i+1} \#(e_j)\choose \#e_{i+1}}.\prod_{i=1}^{l}g(n_i)$$ Intuitively, the second product correspond to the number of way to produce all the sub-trees independently. And the first product correspond to the number of interleaving in such productions.

The probability to generate a particular shape of size $k$ and root $n$ is thus: $$\frac{g(n)}{(k-1)!}$$

On the first shape you gave

 A->B->C
->D


it would give:

$g(C)=g(D)=1$ since $C$ and $D$ are leaves. $g(B)=g(C)=1$. And finally $g(A)={3\choose 1}g(D).g(B)=3$.

Thus the probability is $g(A)/((4-1)!)=1/2$.