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)?

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:[$z*k_1,u*k_1+z*k_2,u*k_2+b*k_1+z*k_3,u*k_3+b*k_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 $\frac{u*k_2}{u*k_2+b*k_1+z*k_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)?