Results 1 to 4 of 4

Math Help - binomial

  1. #1
    Newbie
    Joined
    Jan 2008
    Posts
    3

    binomial

    For natural numbers m<=n calculate (i.e. express by a simple formula not containing a sum) sigma (k=m) to (n) (k choose m) (n choose k).
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by vivian View Post
    For natural numbers m<=n calculate (i.e. express by a simple formula not containing a sum) sigma (k=m) to (n) (k choose m) (n choose k).
    I hope someone comes with a proof by double counting. I want to see one
    I hate combinations proof through algebra.

    But well...

    \boxed{\sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = ??}

    Ans: 2^{n-m} \cdot {n \choose m}

    Solution:

    First we note that {k \choose m}\cdot {n \choose k} = {n \choose m}\cdot {{n-m} \choose {k-m}}
    Let us change variables to make the summation more clearer,
    If k-m=j, then
     \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} = \sum_{j=0}^{j = n-m} {n \choose m}\cdot {{n-m} \choose j}
    So we now get,

    \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}} =  {n \choose m}\cdot {\sum_{j=0}^{n-m}{{n-m} \choose j}} = {n \choose m} \cdot 2^{n-m}

    To get the last step I have used the identity \sum_{j=0}^n{n \choose j} = 2^n
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Opalg's Avatar
    Joined
    Aug 2007
    From
    Leeds, UK
    Posts
    4,041
    Thanks
    7
    Quote Originally Posted by Isomorphism View Post
    I hope someone comes with a proof by double counting. I want to see one
    I hate combinations proof through algebra.
    Here you are, then. Let's count the number of pairs of subsets A\subseteq B\subseteq\{1,2,3,\ldots,n\} such that A contains m elements.

    Method 1. If B contains k elements (where m ≤ k ≤ n) then there are \textstyle{n\choose k} ways of choosing B. For each of these ways, there are \textstyle{k\choose m} ways of choosing A ⊆ B. Thus the total number of ways of choosing the pair {A, B} is \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}}.

    Method 2. This time, choose A first. There are \textstyle{n\choose m} ways of doing this. For each such A, there are n–m elements not in A. Each of these elements has two possibilities: either it is in B or it is not in B (of course, B also contains all the elements of A). That gives 2^{n-m} ways of choosing B. Thus the total number of ways of choosing the pair {A, B} is {n \choose m} \cdot 2^{n-m}.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Thanks Opalg.
    At first I thought this post is suspiciously related to vivian's other post.
    But then I think this was a substep in the other question because if we let m vary from 0 to n, then we get 3^n solutions.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: July 15th 2010, 06:33 AM
  2. Replies: 1
    Last Post: November 12th 2009, 01:38 AM
  3. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: October 2nd 2009, 02:06 PM
  4. Replies: 1
    Last Post: March 12th 2009, 12:09 AM
  5. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 5th 2007, 07:59 AM

Search Tags


/mathhelpforum @mathhelpforum