
38 Combinatorics of Permutations, Second Edition
2
1
2
1
3
3
FIGURE 1.10
The two decreasing non-plane trees on vertex set [3].
13. We say that i is a weak excedance of p = p
1
p
2
···p
n
if p
i
≥ i. Assuming
Theorem 1.36, prove that the number of n-permutations with k weak
excedances is A(n, k).
14. Prove that for all positive integers n,wehave
S(n +1,k+1)=
n
m=k
n
m
S(m, k).
15. A decreasing non-plane tree is a rooted tree on vertex set [n]inwhich
each non-leaf vertex has at most two children, and the label of each
vertex is smaller than that of its parent. See Figure 1.10 for the two
decreasing non-plane trees on vertex set [3]. Let T
n
denote the number
of decreasing ...