Return to Question

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 (sorry, I'm not allowed to include pictures in this post). The image is an extract of Wilf's paper that shows the full procedure Forest. Now, the word adjoined is used in the sentence

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

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

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)

I am writing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf. 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).

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 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.

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

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.

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 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 free unlabelled trees on $n$ vertices.

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 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.