1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Combinatorial Proof
  1. Combinatorial proof? (Replies: 2)

  2. Combinatorial Proof (Replies: 2)

  3. Combinatorial Proof? (Replies: 4)

  4. Combinatorial Proof (Replies: 1)

Loading...