Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: How to prove?

  1. Sep 26, 2011 #1
    1. The problem statement, all variables and given/known data

    If (N,R) indicates number of combinations of R objects selected from set of N objects N >=r then prove :

    E (N,r) x (M,R-r) = (N+M, R)

    E specifies the usual capital sigma notion for a sum.

    3. The attempt at a solution

    Just dont know how to tackle this? Inductive proof may be possible but we have three variables N, M and R, so its non trivial?

    Any clues?
  2. jcsd
  3. Sep 26, 2011 #2

    I like Serena

    User Avatar
    Homework Helper

    Hola the4thamigo_uk! :smile:

    Suppose we have 2 bins with respectively N balls and M balls, and we take a total of R balls from both bins.
    What are the possibilities for the number of balls to take from the first bin?
    And how do they combine with the balls from the second bin?
  4. Sep 26, 2011 #3
    Yes I understand the situation and the combinatoric proof, but how would I formally prove it?
  5. Sep 26, 2011 #4

    I like Serena

    User Avatar
    Homework Helper

    Hmm, let's see....

    Suppose we take generic variables a and b, then:
    (a+b)N+M = (a+b)N (a+b)M

    Working this out you get:
    (.... + C(N+M,R) aR bN+M-R + ... ) = (C(N,0)a0 bN + C(N,1)a1 bN-1 + ...) (C(M,0)a0 bM + C(M,1)a1 bM-1 + ...)

    To get the specific term on the left side, you need to combine the terms on the right side in such a way that corresponds exactly to your equation.
    So the equation must hold true.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook