Combinatorics of Permutations, 2nd Edition

Do Not Look Just Yet. Solutions to Odd-Numbered Exercises. 395

Now let us divide both sides by [n − 1]! to obtain

[n]=[k]q

n−k

+[n −k],

which follows directly from the definition of [m].

23. This can be proved by repeated applications of the result of Exercise 21,

but we prefer a combinatorial argument. The left-hand side provides

the generating function for all k-subsets of [m] according to their subset

sums.

A typical term of the right-hand side is of the form q

m−k−j+1



m−j

k−1



,

where j ∈ [m − k]. We claim that this term will provide the generating

function for those k-subsets of [m] whose largest element is equal to

m − j + 1. Indeed, the rest of such a subset is a (k − 1)-subset of the

set [m − j]. The term q

m−j−k+1

corrects the shift in the definitio