This exercise outlines a bijective proof of the formula

from section 1.1. Let A be the set of k-multisets taken from [n] and let B be the set of k-subsets of [k+n-1]. Assume that the k-multiset

is written in nondecreasing order:

. Define f: A

B by

.

This function, and proof, is originally due to Euler.

Prove that the outputs of

are indeed k-subsets of

. This requires proof since it is not immediately clear from the definition of

.

Proof: Since

and

then we know that the largest output of

is

. Therefore

for any output of

. Since

is the smallest member of [k+n-1] by definition, it follows that any

and that the outputs of

are indeed k-subsets of [k+n-1].