The classification of 231-avoiding permutations by descents and maximum drop

We study the number of 231-avoiding permutations of length $n$ with $j$-descents and maximum drop of less than or equal to $k$, which we denote by $a^{(k)}_{n,j}$.We show that $a^{(k)}_{n,j}$ also counts the number of Dyck paths of length $2n$ with $n - j$ peaks and height $\leq k + 1$, and the number of ordered trees with $n$ edges, $j + 1$ internal nodes, and height $\leq k + 1$. We show that the generating functions for the $a^{(k)}_{n,j} s$ with $k$ fixed satisfy a simple recursion. We also use the combinatorics of ordered trees to prove new explicit formulas for $a^{(k)}_{n,j}$ and prove a simple recursion for the $a^{(k)}_{n,j} s$.

Keywords

permutation statistics, 231-avoiding permutations, descents, drops, trees, Dyck paths

2010 Mathematics Subject Classification

Primary 05A15. Secondary 05E05.

Full Text (PDF format)

Published 31 July 2015