
328 Combinatorics of Permutations, Second Edition
1
2
3
4
5
67
8
8
7
4
56
3
2
1
8
47
6
5
13
2
FIGURE 8.4
A decreasing binary tree and its image under z.
Take the sequence T
1
,T
2
, ···,T
n
. Denote by (T ) the number of left edges of
the forest T ,andbyr(T ) the number of right edges of the forest T .Findthe
smallest index i so that (T
i
) − r(T
i
) = 1. We will now explain why such an
index always exists. If T
2
is a left edge, then (T
2
) − r(T
2
)=1− 0 = 1, and
we are done. Otherwise, at the beginning we have (T
2
) −r(T
2
) < 1, while at
the end we have
(T
n
) − r(T
n
) > ((n − 1) −(n − 3)/2) −(n − 3)/2 > 1,
because of the restriction on k. So at the beginning, (T
j
)−r(T
j
) is too ...