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

Abstract: We study the number of 231-avoiding permutations with

j

-descents and maximum drop is less than or equal to

k

which we denote by

a_{n, 231, j}^{(k)}

. We show that

a_{n, 231, j}^{(k)}

also counts the number of Dyck paths of length

2 n

with

n - j

peaks and height

l e q k + 1

, and the number of ordered trees with

n

edges,

j + 1

internal nodes, and of height

l e q k + 1

. We show that the generating functions for the

a_{n, 231, j}^{(k)}

s with

k

fixed satisfy a simple recursion. We also use the combinatorics of ordered trees to prove new explicit formulas for

a_{n, 231, j}^{(k)}

as a function of

n

in a number of special values of

j

and

k

and prove a simple recursion for the

a_{n, 231, j}^{(k)}

s.

Cited In (3)

This page was built for publication: The classification of 231-avoiding permutations by descents and maximum drop