
410 Combinatorics of Permutations, Second Edition
FIGURE 10.4
A 1-2 tree.
15. As a 132-avoiding permutation is indecomposable if and only if it ends
with its largest entry, the number of such k-permutations is C
k−1
.Let
our three blocks end in positions i, j,andn. With these restrictions, we
clearly have C
i−1
C
j−i−1
C
n−j−1
permutations with the desired property.
Now we have to sum this expression for all possible i and j to get
the total number of 132-avoiding n-permutations having exactly three
blocks. We do this in two steps. First, fix i, and compute the sum
C
i−1
n−1
j=i+1
C
j−i−1
C
n−j−1
= C
i−1
C
n−i−1
.
Second, we sum over all possible i togetthatthereexist
n−