
140 Combinatorics of Permutations, Second Edition
Solutions to Problems Plus
1. This result was first proved by Jeffrey Remmel in [221] as a corollary
to a more general argument involving q-analogues. Other proofs can be
found in [104] and (in a slightly different context), in [268].
2. (a) The proofs are different for the cases of odd n and even n.Thecase
of even n can be proved very similarly to Exercise 61. For odd n,
however, we cannot solely rely on our previous methods, because
2n + 2 is divisible by 4, and so there are permutations counted
by SQ
2n+2
whose odd part is empty. (And therefore, their even
part is of length 2n + 2, and as such, cannot b