
192 Combinatorics of Permutations, Second Edition.
Solutions to Problems Plus
1. First, note that in a 132-avoiding permutation, the entry p
i
is a left-
to-right minimum if and only if either i =1,ori − 1 is a descent.
Therefore, we are looking for the number of 132-avoiding n-permutations
with k descents, or, by taking the reverse, 231-avoiding n-permutations
with k ascents. We know from Exercise 17 that the number of such n-
permutations is equal to the number of northeastern lattice paths from
(0, 0) to (n, n)thathavek north-to-east turns and that never go above
the main diagonal. A comprehensive survey of lattice paths of this and
more general kinds ...