Probability calculation of rooted trees

Question

Given a rooted tree $T_r$ (up to isomorphism), define the probability $P(T_r)$ as the probability of ending up with $T_r$ if one starts with a single (root) vertex and incrementally connects new vertices one-by-one, such that at each step the vertex being connected to on the existing tree is chosen at random

For example: There are 4 4-vertex rooted trees (up to isomorphism). 3 have probability: $1/6$, and 1 has probability: $1/2$

$v$--$v_r$--$v$--$v$

I came up with a Java program for calculating these probabilities, but this is only feasible for trees of up to about 12 or 13 vertices.

The question is: Is there any formula or algorithm for calculating the probability of a tree, based on the attributes of 2 or more of its subtrees?

Answer 1

We can see any tree $T$ as the Hasse diagram of a poset whose smallest element is the root. I will freely identify the tree with the corresponding poset.

If we label by $i$ the $i$'th vertex added in the process, we get a rooted tree equipped with a linear extension, and each such equipped rooted tree occur with probability $\frac{1}{(n-1)!}$ (where $n$ is the number of vertices). The number of ways to get a given rooted tree in this way is the number of linear extensions of this tree up to automorphisms of the rooted tree.

Hence the probability you're looking for is given by $$\frac{L(T)}{|\text{Aut}(T)| (n-1)!}$$ where $L(T)$ is the number of linear extensions of $T$ and $\text{Aut}(T)$ is the automorphism group of $T$. There are algorithms for computing the former in $O(n^2)$ (https://www.researchgate.net/publication/226291352_On_computing_the_number_of_linear_extensions_of_a_tree). I am not sure for the latter, but it can probably be computed efficiently using a variant of the AHU algorithm.