Results 1 to 4 of 4

Thread: 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...

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

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

    Solution:

    First we note that $\displaystyle {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
    $\displaystyle \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,

    $\displaystyle \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 $\displaystyle \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
    10
    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 $\displaystyle 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 $\displaystyle \textstyle{n\choose k}$ ways of choosing B. For each of these ways, there are $\displaystyle \textstyle{k\choose m}$ ways of choosing A ⊆ B. Thus the total number of ways of choosing the pair {A, B} is $\displaystyle \sum_{k=m}^n {{k \choose m}\cdot {n \choose k}}$.

    Method 2. This time, choose A first. There are $\displaystyle \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 $\displaystyle 2^{n-m}$ ways of choosing B. Thus the total number of ways of choosing the pair {A, B} is $\displaystyle {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 $\displaystyle 3^n$ solutions.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 3
    Last Post: Jul 15th 2010, 05:33 AM
  2. Replies: 1
    Last Post: Nov 12th 2009, 12:38 AM
  3. Binomial Theorem or Binomial Coefficient
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: Oct 2nd 2009, 01:06 PM
  4. Replies: 1
    Last Post: Mar 11th 2009, 11:09 PM
  5. Relation between Negative Binomial and Binomial Distros
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: Nov 5th 2007, 06:59 AM

Search Tags


/mathhelpforum @mathhelpforum