A combinatorial proof of a symmetric joint distribution on strict binary trees
Shishuo Fu
原文摘要
Nonplanar strict binary trees on $2n+1$ vertices are enumerated by the reduced tangent numbers $T_{2n+1}/2^n$, whose entries are refined by Poupard's triangle. Poupard defined the end of the minimal chain ($\mathrm{eoc}$) and the parent of the maximum leaf ($\mathrm{pom}$) on these trees, proving that $\mathrm{eoc}$ and $\mathrm{pom}+1$ share this triangular distribution. Foata and Han subsequently showed via tree calculus and partial difference equations that the joint distribution of $(\mathrm{eoc}, 2n+1-\mathrm{pom})$ is symmetric. By introducing an auxiliary tree statistic dual to $\mathrm{eoc}$, we give a bijective proof of this symmetry. Our proof composes a recursive bijection on strict binary trees, a bijection to alternating André permutations, and the reverse-complement involution on permutations.
math.CO · cs.DM