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
Math Forum Home || Math Library || Quick Reference || Math Forum Search