
130 Combinatorics of Permutations, Second Edition
8. (–) Let n be an even positive integer. Prove that at least half of all
permutations of length n contain a cycle of length at least n/2.
9. Let L(n, k)bethenumberofn-permutations whose longest cycle is of
length k. Let us assume that
n
2
<k≤ n.FindaformulaforL(n, k).
10. Let L(n, k) be defined as in the previous exercise.
(a) Let
n
3
<k≤
n
2
.FindaformulaforL(n, k).
(b) (+) Now let 1 <k<n.FindaformulaforL(n, k).
11. An adjacent transposition is a transposition interchanging two consecu-
tive entries in a permutation, that is, it is a cycle of the form (ii+1).
Prove that any element of S
n
can be obtained as a