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: Combinatorial Proof

  1. Apr 8, 2007 #1
    I have a bunch of equations that I must prove 'using combinatorics', which means double counting or some sort of bijective mapping. I haven't done this before, and I'd like to know, as an example, how the following can be proved 'combinatorially':

    [tex]\left(\begin{array}{cc}{n+1}\\{m+1}\end{array}\right)=\sum_{i=0}^{n-m}\left(\begin{array}{cc}{m+i}\\m\end{array}\right)[/tex]
     
  2. jcsd
  3. Apr 9, 2007 #2
    Notice the left hand side counts the number of bitstrings of length n + 1 containing m + 1 ones.
     
  4. Apr 9, 2007 #3
    look at ways of choosing m+1 elements from n+1 objects.

    the series tells you that you sum up the ways of choosing m objects from m+i objects. but you want to choose m+1 objects; so what happens to the m+1th element?

    hint1: read the sum backward
    [tex]\sum_{i=n-m}^{0}\binom{m+i}{m}[/tex]
    (i keeps decreasing, not increasing)
    hint2: choose 1 element first, then choose the other m elements.

    if that isn't enough,
    hint3: look at the position of the first element when choosing...
     
    Last edited: Apr 9, 2007
  5. Apr 9, 2007 #4
    Shouldn't it be multiplied instead of summed?
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook