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?

  >   nCk*mC(r-k)=(n+m)Cr


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!   
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- The Math Forum at NCTM. All rights reserved.