Diagonally convex directed polyominoes and even trees: A bijection and related issues (Q1849976)

The authors present a simple bijection between diagonally convex directed (DCD) polyominoes with \(n\) diagonals and plane trees with \(2n\) edges in which every vertex has even degree (even trees), which specializes to a bijection between parallelogram polyominoes and full bniary trees. They next consider a natural definition of symmetry for DCD polyominoes, even trees, ternary trees, and non-crossing trees, and show that the number of symmetric objects of a given size is the same in all four cases, proving Theorem 1: The number of symmetric objects of size \(n\) is the same in all cases. Moreover, it is given by \[ s_n= \begin{cases} {1\over n+1} {3n/2\choose n/2}\quad &\text{if }n\text{ is even}\\ {2\over n+1} {(3n-1)/2\choose (n-1)/2}\quad &\text{if }n\text{ is odd}\end{cases}. \]