18 Combinatorics of Permutations, Second Edition
lattice paths with n edges, exactly k of which are vertical. (Note the shift in
parameters: |A(n, k)| = A(n, k + 1), but this will not cause any confusion.)
Let P(n) be the set of labeled northeastern lattice paths that have edges
a
1
,a
2
,...,a
n
and that corresponding positive integers e
1
,e
2
,...,e
n
as labels,
so that the following hold:
(i) the edge a
1
is horizontal and e
1
=1,
(ii) if the edges a
i
and a
i+1
are both vertical, or both horizontal, then
e
i
≥ e
i+1
,
(iii) if a
i
and a
i+1
are perpendicular to each other, then e
i
+ e
i+1
≤ i +1.
The starting point of a path in P(n) has no additional significance. Let
P(n, k) be the set of all lattice paths in P(n) which have k vertical edges, and
let P (n, k)=|P(n, k)|.
PROPOSITI ...