# 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
Show Scanned Page ##### MSC:
 05C05 Trees 05C30 Enumeration in graph theory 05A10 Factorials, binomial coefficients, combinatorial functions
Full Text: