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].
Please critique this proof. Thanks