Originally Posted by

**oldguynewstudent** This exercise outlines a bijective proof of the formula $\displaystyle \left(\left({n\atop k}\right)\right)= \left({k+n-1\atop k}\right)$ 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 $\displaystyle \left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ is written in nondecreasing order: $\displaystyle a_{1}\leq a_{2}\leq\ldots\leq a_{k}$. Define f: A $\displaystyle \longrightarrow$ B by

$\displaystyle f\left(\left\{ a_{1},a_{2},\ldots,a_{k}\right\} \right)=\left\{ a_{1},a_{2}+1,a_{3}+2,\ldots,a_{k}+n-1\right\}$ .

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

Prove that the outputs of $\displaystyle f$ are indeed k-subsets of $\displaystyle [k+n-1]$ . This requires proof since it is not immediately clear from the definition of $\displaystyle f$.

Proof: Since $\displaystyle f(a_{i})=a_{i}+i-1, 1 \leq i \leq k$ and $\displaystyle a_{1}\leq a_{2}\leq\ldots\leq a_{k}$ then we know that the largest output of $\displaystyle f$ is $\displaystyle a_{k}+k-1$. Therefore $\displaystyle a_{1}\leq a_{i}+i-1\leq a_{k}+k-1, 1 \leq i \leq k$ for any output of $\displaystyle f$ . Since $\displaystyle a_{1}$ is the smallest member of [k+n-1] by definition, it follows that any $\displaystyle (a_{i}+i-1)\subseteq[k+n-1], 1 \leq i \leq k$ and that the outputs of $\displaystyle f$ are indeed k-subsets of [k+n-1].