I'm looking for closed (possibly approximate) formulae for the following problem.
I am trying to generate (uniformly distributed) random trees of a given size n. The "size" is the number of symbols in the tree, and I have fixed numbers of distinct nullary, unary and binary symbols available. To create a uniform distribution I need to know the number of trees of a certain characteristics, or at least their relative frequencies. "Uniform" means in this case that every possible tree of size n is picked with equal probability.
The trees can be seen as strings of symbols in Polish notation, and instead of just counting the full strings of a fixed size one can count prefixes of those strings with respect to a certain arity (number of holes in a tree, 0 holes is a complete tree). These numbers obey a straightforward recurrence relation: if, at size n, we have k_0 tree fragments of arity 0, k_1 of arity 1, etc. (write it as n:[k_0,k_1,k_2,k_3,...]) then at size n+1 this list becomes: n+1:[zk_1,uk_1+zk_2,uk_2+bk_1+zk_3,uk_3+bk_2+z*k_4,...], where z,u,b are the numbers of nullary, unary, and binary symbols - because a unary symbol does not change the arity of a tree, binary/nullary make it go up/down by 1, and trees of arity 0 cannot be further extended. For example, trees of arity 0 must have a nullary symbol in last position, so the number of those trees at size n+1 is z times the number of unary trees of size n.
I can use this recurrence to compute precise numbers, but they get huge quickly, and for large n the computation takes very long, as we are talking here arbitrary precision integers and exponential growth. (For n=10000, my computer is huffing and puffing for several minutes to compute those numbers. n=100000 would be hopeless.)
The kind of numbers I need to generate random trees are probabilities such as uk_2/(uk_2+bk_1+zk_3), which in this case would be the probability that a prefix string of length n+1 and arity 2 has a unary function symbol in its last position. So, are there closed formulae that describe the numbers of those tree fragments (or their relative proportions)?
