
390 Combinatorics of Permutations, Second Edition
In other words, the set of n-permutations with k peaks consists of the
entire set of n-permutations with 2k + 1 alternating runs, half of the n-
permutations with 2k alternating runs, and half of the n-permutations
with 2k + 2 alternating runs. This proves
Peak(n, k)=G(n, 2k +1)+
G(n, 2k)+G(n, 2k +2)
2
.
35. It is easy to prove, by induction, or otherwise, that the number of de-
scents of p is equal to the number of right edges of T (p), while the
number of ascents of p is equal to the number of left edges of T (p). Now
it is clear that the symmetry of the sequence A(n, k)
k
can be proved by
the simple bijection ...