Results 1 to 2 of 2

Math Help - Proof of k-multiset coefficients, part 1

  1. #1
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244

    Proof of k-multiset coefficients, part 1

    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
    Last edited by oldguynewstudent; June 18th 2010 at 07:29 PM. Reason: add limits for i
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Member oldguynewstudent's Avatar
    Joined
    Oct 2009
    From
    St. Louis Area
    Posts
    244
    Quote Originally Posted by oldguynewstudent View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Circular Permutations of a Multiset
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: January 22nd 2010, 04:13 AM
  2. Multiset Addition Rule (proof required)
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: August 31st 2009, 07:21 AM
  3. Multiset
    Posted in the Statistics Forum
    Replies: 2
    Last Post: May 21st 2009, 03:41 AM
  4. Homogeneous Equations with Constant Coefficients Part II
    Posted in the Differential Equations Forum
    Replies: 1
    Last Post: April 19th 2009, 05:36 PM
  5. Multiset
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 27th 2008, 01:31 PM

Search Tags


/mathhelpforum @mathhelpforum