Proof of k-multiset coefficients, part 1

**oldguynewstudent** · June 18th 2010, 03:21 PM

This exercise outlines a bijective proof of the formula $\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 $\left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ is written in nondecreasing order: $a_{1}\leq a_{2}\leq\ldots\leq a_{k}$ . Define f: A $\longrightarrow$ B by
$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 $f$ are indeed k-subsets of $[k+n-1]$ . This requires proof since it is not immediately clear from the definition of $f$ .

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

Please critique this proof. Thanks

**oldguynewstudent** · June 19th 2010, 03:55 AM

Originally Posted by oldguynewstudent

This exercise outlines a bijective proof of the formula $\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 $\left\{ a_{1},a_{2},\ldots,a_{k}\right\}$ is written in nondecreasing order: $a_{1}\leq a_{2}\leq\ldots\leq a_{k}$ . Define f: A $\longrightarrow$ B by
$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 $f$ are indeed k-subsets of $[k+n-1]$ . This requires proof since it is not immediately clear from the definition of $f$ .

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

b) Prove that f is a bijection.

Proof: Let $f(a_{i1})=f(a_{i2})$ .We need to show that $a_{i1}=a_{i2}$ . Now suppose that $a_{i1}\neq a_{i2}$ , then we have two cases:

Case1: $a_{i1}<a_{i2}$ . We know that $f(a_{i1})=a_{i1}+i1-1$ and $f(a_{i2})=a_{i2}+i2-1$ . If $a_{i1}<a_{i2}$ then since the set is written in nondescending order, we know that $i1<i2$ . If we add the inequalities together, we get $a_{i1}+i1<a_{i2}+i2$ . Now subtract 1 from both sides preserving the inequality to obtain $a_{i1}+i1-1<a_{i2}+i2-1$ which is a contradiction.

Case2: $a_{i1}>a_{i2}$ . Similarly, we have $i1>i2$ , so we get $a_{i1}+i1>a_{i2}+i2$ , and subtracting 1 from both sides we get $a_{i1}+i1-1>a_{i2}+i2-1$ ,which is again a contradiction.

Therefore, $a_{i1}=a_{i2}$ which proves that $f$ is injective. Since $f$ is both injective and onto, it is a bijection. QED

Please critique this proof. Thanks

Thread: Proof of k-multiset coefficients, part 1

LinkBack

Thread Tools

Display

Proof of k-multiset coefficients, part 1

Similar Math Help Forum Discussions

Circular Permutations of a Multiset

Multiset Addition Rule (proof required)

Multiset

Homogeneous Equations with Constant Coefficients Part II

Multiset

Search Tags