Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Combinatorial Proof


Date: 6/13/96 at 17:29:38
From: Anonymous
Subject: combinatorial proof

Could you please prove the following combinatorial proof?

  r
-----|
 \
  >   nCk*mC(r-k)=(n+m)Cr
 /
-----|
 k=0

   thanks,
     Mike


Date: 6/14/96 at 5:29:51
From: Doctor Anthony
Subject: Re: combinatorial proof

This is proved by considering the following identity:

 (1+x)^n*(1+x)^m = (1+x)^(n+m)

If you expand both brackets on the left hand side by the binomial 
theorem and pick out the products that give the term in x^r, then the 
sum of these coefficients will equal the coefficient of x^r on the 
right hand side.  This we know is (n+m)Cr.  

For example nC0*mCr + nC1*mC(r-1) + ... will 
be the coefficients found by taking 1 from the first bracket and the 
coefficient of x^r from the second bracket, plus the coefficient 
of x from the first bracket and the coefficient of x^(r-1) from 
the second bracket, and so on and so on.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/   
    
Associated Topics:
High School Discrete Mathematics
High School Permutations and Combinations

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/