Achiral plane trees

✍ Scribed by Nicholas Wormald

• Publisher: John Wiley and Sons
• Year: 1978
• Tongue: English
• Weight: 899 KB
• Volume: 2
• Category: Article
• ISSN: 0364-9024
• DOI: 10.1002/jgt.3190020303

✦ Synopsis

Abstract

Harary and Robinson showed that the number a~n~ of achiral planted plane trees with n points coincides with the number p~n~ of achiral plane trees with n points, for n ⩾ 2. They posed the problem of finding a natural structural correspondence which explains this coincidence. In the present paper this problem is answered by constructing two‐to‐one correspondences from certain sets of binary sequences to each of the sets of trees concerned, giving a structural basis for the equation 2__a__~n~ = 2__p__~n~. Answers are also supplied to similar correspondence‐type problems of Harary and Robinson, concerning planted plane trees, and achiral rooted plane trees. In addition, each of these four types of plane trees are counted with numbers of points and endpoints as the enumeration parameters. The results all show a symmetry with respect to the number of endpoints which is not shared by the set of all plane trees.