In this paper, we provide a bijection between subsets of ordered trees with n edges where no two vertices at the same level have di?erent parents and those with height at most three. We show that the number of these subsets of ordered trees corresponds to every other Fibonacci number, and provide a combinatorial interpretation of Chen and Shapiro’s generalization of this sequence using k-trees. We also prove Shapiro’s identity involving the generating function of this sequence and Riordan arrays.
展开▼