I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (*The uniform selection of trees*. 1981. In *Journal of Algorithms*). This paper defines the procedure `Free`

which generates free unlabelled trees by calling one of two smaller procedures (either `Bicenter`

or `Forest`

) with a certain probability each. These two procedures, in turn, are based on the *ranrut* procedure, which generates rooted unlabelled trees uar. You can find the reference in *Combinatorial Algorithms For Computers and Calculators*. Albert Nijenhuis and Herbert S. Wilf. 2nd Edition. Academic Press. (I'll try to make this post as self-contained as I can).

First, I'm quite convinced to have managed to implement the *ranrut* procedure so that each rooted unlabelled tree is generated uar. However, I'm having some problems with the algorithm to generate free unlabelled trees (here) and I was hoping that you could help me. In this post I would like to ask two questions.

I have one problem with language. Specifically, with one particular word, which I do not understand in the context of the paper. The word is *adjoined* and appears in the `Forest`

procedure, as seen highlighted in this image:

The image is an extract of Wilf's paper that shows the full procedure `Forest`

. Now, the word *adjoined* is used in the sentence

Then exit with $j$ copies of $T'$

adjoinedto $\mathcal{F}'$.

- Should
*adjoined*be understood here as the disjoint union of graphs? Namely, should I perform the operation $\mathcal{F}' \oplus T'_1 \oplus \cdots T'_j$, where $\oplus$ denotes disjoint union of graphs ? If not, how should I interpret it?

Wilf says that, in order to generate uar a forest of $m$ trees, we first choose two integers $(j,d)$ with probability (as shown in the above image)

$$ Prob(j,d) = \frac{d\cdot \alpha(m - jd,q) \cdot a_d}{m \cdot \alpha(m,q)}. $$

For this we need the values $a_n$ (the number of rooted unlabelled trees of $n$ vertices), and $\alpha(m,q)$ (the number of rooted forests of $m$ vertices whose trees have at most $q$ vertices each).

I have written an algorithm to correctly calculate $a_n$. I know it is correct because I can compare the values obtained with its integer sequence.

- I would like to know if I'm calculating $\alpha(m,q)$ correctly. However, I haven't been able to find the integer sequences for $\alpha(m,q)$. Do you know where I can find it?

I hope to have made my doubts understandable and the questions clear.

Thanks to you all for your time.

**Edit**
This post was motivated because my implementation of this algorithm did not generate trees uniformly at random. In my desperation I came here for help. Although the questions above still stand (because the implementation of the above might still be wrong), one of the "bugs" was caused by an error in Wilf's paper. My advisor pointed me to this document (*Graph theory package for Giac/Xcas - Reference Manual*, September 2018) where this error is mentioned and corrected (page 38, footnote 1.1). For the sake of self-containment, I tell you here what the error is and how it has been corrected. The `Free`

procedure that Wilf defines in this paper, says that in order to generate an $n$-vertex free tree u.a.r. you have to generate a bicentroidal tree with probability $p$, or a random forest of $n-1$ vertices with probability $1-p$ (the roots of this forest are connected to a new vertex). Wilf says that
$$p ={1 + a_{n/2} \choose 2}/a_n$$
where $a_n$ is the number of rooted unlabelled trees of $n$ vertices. As pointed out in the cited document in this edit, the denominator is wrong. Instead of $a_n$, it should be $f_n$, the number of unlabelled free trees on $n$ vertices.

4more comments