Contents Online

# Journal of Combinatorics

## Volume 6 (2015)

### Number 4

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

Pages: 509 – 534

DOI: https://dx.doi.org/10.4310/JOC.2015.v6.n4.a6

#### Authors

#### Abstract

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.

Published 31 July 2015