
366 Combinatorics of Permutations, Second Edition
s in the traditional sense.
PROPOSITION 9.17
Let a, b,andz
be defined as above, and let s
=(12···(n +1))z
.Thenwe
have
1. c(Γ(s
)) = c(Γ(s)) − 1 if 2 ≤ a,anda − 1 and z(1) are not in the same
cycle of s,
2. c(Γ(s
)) = c(Γ(s)) + 1 if 2 ≤ a,anda −1 and z(1) are in the same cycle
of s,and
3. c(Γ(s
)) = c(Γ(s)) + 1 if a =1.
PROOF Let us assume first that a ≥ 2, and that a − 1 is in a cycle C
1
of s,andz(1) is in a different cycle C
2
of s.LetC
1
=((a − 1)b ···) and let
C
2
=(z(1) ···n). After the insertion of n+1 into z, the obtained permutation
s
=(12···(n +1))z
sends a −1ton +1, then n +1 to z(1), then leaves the
rest ...