zbMATH — the first resource for mathematics

Correspondences between plane trees and binary sequences. (English) Zbl 0205.54702
A typical example of the correspondence described is the following. Let \((e_1,\ldots,e_{2n})\) denote a sequence of \(0\)’s and \(1\)’s containing exactly \(n\) \(1\)’s such that \(e_1+\ldots+e_{2i}\geq 1\) for \(i=1,\ldots,n\). Every sequence of this kind corresponds to a representative of a unique class of isomorphic planted plane trees having \(n+3\) vertices. A diagram representing the tree can be drawn in the plane by interpreting the sequence as follows:
First, adjoin \((e_{-2},e_{-1},e_0)=(1,0,1)\) on the left of the sequence, then adjoin \((e_{2n+1},e_{2n})=(0,0)\) on the right. The \(n+3\) vertices of the tree are the numbers \(0,\ldots,n+2\); the root is \(0\), and the vertex joined to the root is \(1\). Now, if \(e_i=0\), \(e_{i+1}=\ldots=e_{i+j}=1\), and \(e_{i+j+1}=0\) where \(i\geq -1\), \(j\geq 0\), then the vertex \(1+i=(e_1,\ldots,e_i)\) has exactly \(j\) edges drawn upwards to new vertices numbering consecutively \(e_{-2}+\ldots+e_{i+1}\) to \(e_{-2}+\ldots+e_{i+j}\) from left to right. This also means that if \(e_i=e_{i+1}=0\) (that is, \(j=0\)), then the vertex \(1+i-(e_1+\ldots+e_i)\) has no edges drawn upward from it.
The same set of binary sequences can be used to describe equivalence classes of isomorphic trivalent planted trees having \(2n+4\) vertices. Thus, a one-to-one correspondence between these two sets of trees is induced which is considerably simpler than the one originally found by F. Harary, G. Prins and W. T. Tutte [Nederl. Akad. Wet., Proc., Ser. A 87, 319–329 (1964; Zbl 0126.19002)]. Enumeration problems involving classes of isomorphic planted plane trees with various restrictions on the degrees of the vertices are discussed. Generating functions are used, and \(k\)-valent trees are enumerated. (There are \(\frac1n \binom{kn}{n-1}\) classes of isomorphic \((k+1)\)-valent planted plane trees with \(kn+2\) vertices.) Also, a method is indicated for enumerating plane trees embedded in the plane on certain networks. One of the examples is particularly elegant, and gives an upper bound for the number of \(n\)-ominoes. Finally, various binomial identities are proved as a by-product of the combinatorial problems studied in the paper.
Reviewer: David A. Klarner

05C05 Trees
05C30 Enumeration in graph theory
05A10 Factorials, binomial coefficients, combinatorial functions
Full Text: DOI