Skip to main content
3 of 3
removed capitals from title
YCor
  • 63.9k
  • 5
  • 187
  • 286

Probability calculation of rooted trees

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?

swami
  • 375
  • 1
  • 6