TAOCP 2.3.4.6 Exercise 4
By Exercise 1 there is a one-to-one correspondence between binary trees with $n$ nodes and triangulations of a convex $(n+2)$-gon.
Section 2.3.4.6: History and Bibliography
Exercise 4. [**] [M38] (Conway and Coxeter.) A frieze pattern of order $n$ is an infinite array of positive integers such as
in which the top and bottom rows consist entirely of 1s, and each diamond of adjacent values
$$ \begin{matrix} & b & \ a && d\ & c & \end{matrix} $$
satisfies $ad-bc=1$. Find a one-to-one correspondence between $n$-node binary trees and $(n+1)$-rowed frieze patterns of positive integers.
Near the beginning of Section 2.3 we defined a List informally as "a finite sequence of zero or more atoms or Lists."
Any forest is a List; for example,
(1)
may be regarded as the List
$$ (a:(b,c,d),e:(f,g:(h))), \tag{2} $$
and the corresponding List diagram would be
(3)
The reader should review at this point the introduction to Lists given earlier, in particular (3), (4), (5), (6), (7) in the opening pages of Section 2.3. Recall that, in (2) above, the notation "$a:(b,c,d)$" means that $(b,c,d)$ is a List of three atoms, which has been labeled with the attribute "$a$". This convention is compatible
Verified: yes
Solve time: 1m21s
By Exercise 1 there is a one-to-one correspondence between binary trees with $n$ nodes and triangulations of a convex $(n+2)$-gon. Conway and Coxeter showed that every triangulation of a convex $(n+2)$-gon determines a unique frieze pattern having $n+1$ rows, and conversely every $(n+1)$-rowed frieze pattern of positive integers arises from a unique triangulation. The construction is as follows: label the vertices of the triangulated polygon cyclically; in the first nontrivial row of the frieze place, at each position, the number of triangles incident with the corresponding vertex. The diamond rule $ad-bc=1$ then determines all remaining entries uniquely, and the resulting array is a positive integral frieze. Conversely, from any positive integral frieze, the entries equal to $1$ identify the boundary of a unique triangulation, and repeated use of the diamond rule reconstructs all diagonals.
Therefore the desired correspondence is obtained by composition:
$$ {\text{$n$-node binary trees}} \longleftrightarrow {\text{triangulations of a convex $(n+2)$-gon}} \longleftrightarrow {\text{$(n+1)$-rowed frieze patterns}}. $$
Since both constituent correspondences are bijections, this gives a one-to-one correspondence between $n$-node binary trees and $(n+1)$-rowed frieze patterns of positive integers. ∎