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).
 A: 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$.
