
162 Combinatorics of Permutations, Second Edition.
0
0
00
0
0
3
1
2
1
0
FIGURE 4.2
A β(0, 1)-tree.
• if v is an internal node and v
1
,v
2
, ···,v
k
are its children, then the in-
equality (v) ≤ 1+
k
i=1
(v
k
) holds. (This explains the number 1 in the
name of β(0, 1)-trees.)
Example 4.31
Figure 4.2 shows a β(0, 1)-tree on 12 vertices.
Let us call a permutation p = p
1
p
2
···p
n
indecomposable if there exists no
k ∈ [n − 1] so that for all i ≤ k<j,wehavep
i
>p
j
.Inotherwords,p is
indecomposable if it cannot be cut into two parts so that everything before
the cut is larger than everything after the cut. For instance, 3142 is inde-
composable, but 43512 is not as we could choose ...