Simple Random Sampling of Binary Forests with Fixed Number of Nodes and Trees

We generalize the classical algorithm of Rémy for random sampling of full binary trees with given number of leaves. As a result, we give a simple linear time algorithm for random generation of full binary forests with given number of trees and leaves. The algorithm is obtained from an elegant bijection that we construct in order to give a direct proof of the well-known fact that these forests are counted by the k-th fold self-convolution of the Catalan numbers. Via some well-known bijections, the given algorithm can be used to sample random objects from several other classes enumerated by self-convolutions of the Catalan numbers, e.g., binary forests with given number of trees, lists of given number of balanced strings and others.