Why is the sum of (nCk)*(mCr-k) equal to (m+n)Cr?

[Masaru]

I am struggling with the following question:

Prove the sum of (nCk)*(mCr-k) = (m+n)Cr?

In other words, we are required to prove:

(mC0)*(nCr) + (mC1)*(nCr-1) + (mC2)*(nCr-2) +....+ (mCr-1)*(nC1) + (mCr)*(nC0) = (m+n)Cr.

I simply expanded it as follows:

n!/r!(n-1)! + m*n!/(r-1)!(n-r+1)! + m!*n!/2!(m-2)!(r-2)!(n-r+2)! +.....+ m!*n/(r-1)!(m-r+1)! + m!/r!(m-r)!

But I am stuck and cannot go further than this and have no idea how it can end up with

(m+n)Cr.

I did lots of google search for this type of question, and it seems that it is called "combinatorial proof" according to my google search and may require the knowledge of "binomial theorem".

However, this question comes from a section of textbook placed BEFORE the section about "binomial theorem" so there must be a way to work it out without the knowledge of it.
​

I would much appreciate it if someone can help me with this question in a step-by-step manner that I can easily follow and understand.

Thank you.

 

[Denis]

Prove the sum of (nCk)*(mCr-k) = (m+n)Cr

You mean the product, not the sum, right?

Let k=3, m=8, n=6, r=5

(nCk)*(mCr-k) = 1060

(m+n)Cr = 2002

Seems to be something wrong with your equation...Unless I goofed!

 

[Deleted member 4993]

Actually the question is to prove:

\(\displaystyle \displaystyle{\sum_{k=0}^r \left [nC_k \ * \ mC_{(r-k)}\right ] = (n+m)C_r}\)

Go to http://mathforum.org/library/drmath/view/54223.html

for a start......

 

[Dr.Peterson]

There is a much easier way to do this.

The right side is the number of ways to choose r out of m+n items. Suppose, for example, that there are m men and n women, from whom we want to select a committee of r people.

Do you see that each of these committees will consist of some number k of men, and r - k women?

 

[Masaru]

I do not understand it.

Actually the question is to prove:

\(\displaystyle \displaystyle{\sum_{k=0}^r \left [nC_k \ * \ mC_{(r-k)}\right ] = (n+m)C_r}\)

Go to http://mathforum.org/library/drmath/view/54223.html

for a start......

Yes, I had a look at this website even before I posted this question, but I just could not understand even why it is relevant to this question. As I said, this is supposed to be a question that you can work out without the knowledge of binomial theorem.

 

[pka]

Yes, I had a look at this website even before I posted this question, but I just could not understand even why it is relevant to this question. As I said, this is supposed to be a question that you can work out without the knowledge of binomial theorem.

Did you read carefully reply #4? This proof does no require knowledge of the binomial expansion.
Lets take off from reply # 4. If there are m men and n women and we choose a committee of r from that group.
There \(\displaystyle \binom{M+N}{r}\) ways to do that.
BUT any of those committees will consist of k men & r-k women, where \(\displaystyle 0\le k\le r\)
Now can you see a sum there?

 

[Dr.Peterson]

Yes, I had a look at this website even before I posted this question, but I just could not understand even why it is relevant to this question. As I said, this is supposed to be a question that you can work out without the knowledge of binomial theorem.

Try my suggestion, which doesn't require knowledge of the binomial theorem, and is a combinatorial proof (which means that it is based not on algebra, but on counting the same thing two different ways).

(I was trying much of the day to get my answer to go through without producing an error.)

 

[Masaru]

Thank you. I think that I finally got it.

Did you read carefully reply #4? This proof does no require knowledge of the binomial expansion.
Lets take off from reply # 4. If there are m men and n women and we choose a committee of r from that group.
There \(\displaystyle \binom{M+N}{r}\) ways to do that.
BUT any of those committees will consist of k men & r-k women, where \(\displaystyle 0\le k\le r\)
Now can you see a sum there?

Thank you. I think that I finally got it.

If you expand the left-hand side, it will be something like:

(nC0)*(mCr) + (nC1)*(mCr-1) + (nC2)*(mCr-2) +....+ (nCr-1)*(mC1) + (nCr)*(mC0).

If "m" refers to the number of men in a committee and "n" refers to the number of women in the same committee, then

the first term

(nC0)*(mCr) gives us the number of ways you can arrange an committee where there is no woman and "r" number of all men,

the second term

(nC1)*(mCr-1) gives us the number of ways you can arrange an committee where there is 1 woman and "r-1" number of men - here the number of men is "r-1" because the number of men plus the number of women in a committee has to be always "r".

If you keep working out like this, then finally the last term

(nCr)*(mC0) gives us the number of ways you can arrange an committee where you have "r" number of women and no men.

The above process covers all the cases and ways you can arrange an committee of "r" members from "m" number of men and "n" number of women, which is exactly the same as the ways you can arrange an committee of "r" members from "m + n" number of people.

In other words, the left-hand side is a method to find out the total number of ways you can arrange a committee by splitting "m + n" number people into two groups - a group of "m" number of people and another for "n" number of people and adding up all the numbers of ways for each case (Case 1: nothing from the first group & "r" from the second one; Case 2: 1 from the first group & "r-1" from the second one, etc)​

​

​

​

 

[Masaru]

Thank you very much for your help.

Try my suggestion, which doesn't require knowledge of the binomial theorem, and is a combinatorial proof (which means that it is based not on algebra, but on counting the same thing two different ways).

(I was trying much of the day to get my answer to go through without producing an error.)

I think that now I understand.

Thank you very much for your help, Dr. Peterson.

If you expand the left-hand side, it will be something like:

(nC0)*(mCr) + (nC1)*(mCr-1) + (nC2)*(mCr-2) +....+ (nCr-1)*(mC1) + (nCr)*(mC0).

If "m" refers to the number of men in a committee and "n" refers to the number of women in the same committee, then

the first term (nC0)*(mCr) gives us the number of ways you can arrange an committee where there is no woman and "r" number of all men,

the second term

(nC1)*(mCr-1) gives us the number of ways you can arrange an committee where there is 1 woman and "r-1" number of men - here the number of men is "r-1" because the number of men plus the number of women in a committee has to be always "r".

If you keep working out like this, then finally the last term

(nCr)*(mC0) gives us the number of ways you can arrange an committee where you have "r" number of women and no men.

The above process covers all the cases and ways you can arrange an committee of "r" members from "m" number of men and "n" number of women, which is exactly the same as the ways you can arrange an committee of "r" members from "m + n" number of people.

In other words, the left-hand side is a method to find out the total number of ways you can arrange a committee by splitting "m + n" number people into two groups - a group of "m" number of people and another for "n" number of people and adding up all the numbers of ways for each case (Case 1: nothing from the first group & "r" from the second one; Case 2: 1 from the first group & "r-1" from the second one, etc)​

​

​

 

[Dr.Peterson]

I think that now I understand.

Thank you very much for your help, Dr. Peterson.

If you expand the left-hand side, it will be something like:

(nC0)*(mCr) + (nC1)*(mCr-1) + (nC2)*(mCr-2) +....+ (nCr-1)*(mC1) + (nCr)*(mC0).

If "m" refers to the number of men in a committee and "n" refers to the number of women in the same committee, then

the first term (nC0)*(mCr) gives us the number of ways you can arrange an committee where there is no woman and "r" number of all men,

the second term

(nC1)*(mCr-1) gives us the number of ways you can arrange an committee where there is 1 woman and "r-1" number of men - here the number of men is "r-1" because the number of men plus the number of women in a committee has to be always "r".

If you keep working out like this, then finally the last term

(nCr)*(mC0) gives us the number of ways you can arrange an committee where you have "r" number of women and no men.

The above process covers all the cases and ways you can arrange an committee of "r" members from "m" number of men and "n" number of women, which is exactly the same as the ways you can arrange an committee of "r" members from "m + n" number of people.

In other words, the left-hand side is a method to find out the total number of ways you can arrange a committee by splitting "m + n" number people into two groups - a group of "m" number of people and another for "n" number of people and adding up all the numbers of ways for each case (Case 1: nothing from the first group & "r" from the second one; Case 2: 1 from the first group & "r-1" from the second one, etc)
​

​

​

Nicely explained! (But I'd avoid the word "arrange", which suggests that order matters.)

Did you notice what happens if m < r, or n < r? We don't normally consider this case. For example, try evaluating both sides for (2+3)C4.

 

[Masaru]

I would work out like this.

​

Nicely explained! (But I'd avoid the word "arrange", which suggests that order matters.)

Did you notice what happens if m < r, or n < r? We don't normally consider this case. For example, try evaluating both sides for (2+3)C4.

Ok, then I will use the word "organise (a committee)" instead of "arrange".

Right-hand side = ​

(2+3)C4 = 5C4 = 5
​

Left-hand side = (2C0)*(3C4)+ (2C1)*(3C3) + (2C2)*(3C2) + (2C3)*(3C1) + (2C4)*(3C0)


This is like finding out the number of ways you can organise a committee of 4 members from 2 men and 3 women.

(2C0)*(3C4) gives us the number of ways you can organise a committee where you have no men, which is impossible because you would need 4 women but you have only 3 women, so this renders 0.

The fourth term (2C3)*(3C1) also gives us the number of ways you can organise a committee where you have 3 men, which is again impossible because you have only 2 men, so this again would give us 0.

The last term (2C4)*(3C0), for the similar reason, gives us 0 because it is impossible to do (2C4).

Therefore, the answer would be (2C1)*(3C3) + (2C2)*(3C2) = 2 + 3 = 5, which is the same as the right-hand side.​

​

​

​

​

​

​

​

​

​

​

​

​

 

[Dr.Peterson]

​

Ok, then I will use the word "organise (a committee)" instead of "arrange".

Right-hand side = ​

(2+3)C4 = 5C4 = 5
​

Left-hand side = (2C0)*(3C4)+ (2C1)*(3C3) + (2C2)*(3C2) + (2C3)*(3C1) + (2C4)*(3C0)


This is like finding out the number of ways you can organise a committee of 4 members from 2 men and 3 women.

(2C0)*(3C4) gives us the number of ways you can organise a committee where you have no men, which is impossible because you would need 4 women but you have only 3 women, so this renders 0.

The fourth term (2C3)*(3C1) also gives us the number of ways you can organise a committee where you have 3 men, which is again impossible because you have only 2 men, so this again would give us 0.

The last term (2C4)*(3C0), for the similar reason, gives us 0 because it is impossible to do (2C4).

Therefore, the answer would be (2C1)*(3C3) + (2C2)*(3C2) = 2 + 3 = 5, which is the same as the right-hand side.​

​

​

​

​

​

​

​

​

​

​

​

​

Correct.

My point here was simply that the usual formula for combinations does not apply when r>n; in fact, my calculator gives an error when I ask it for 3C4. You are aware that the correct value to use there is 0. With that understanding, the formula we proved is correct.

But words are funny -- to my mind, at least, "organize" also suggests order! Some things can't be said as clearly as one wants to.