Combinatoric Identity r*nCr = n*(n-1)C(r-1): What does this identity mean?

[Steven G]

I just saw that r*nCr = n*(n-1)C(r-1) where nCr = # of ways to choose r objects from n objects. I was easily able to prove it to convince myself that it is true.

My question is what does it really say, that is what does this identity mean?

 

[Dr.Peterson]

I just saw that r*nCr = n*(n-1)C(r-1) where nCr = # of ways to choose r objects from n objects. I was easily able to prove it to convince myself that it is true.

My question is what does it really say, that is what does this identity mean?

Interesting.

Let's take an example. With n=5, r=3, you have 3*5C3 = 3*10 = 30, and 5*4C2 = 5*6 = 30.

Looking for a way to see both sides as different ways to count the same things, I see that 3*5C3 is the number of ways to choose 3 of abcde and mark one as special (here, capitalized):

Abc Abd Abe Acd Ace Ade Bcd Bce Bde Cde
aBc aBd aBe aCd aCe aDe bCd bCe bDe cDe
abC abD abE acD acE adE bcD bcE bdE cdE

Do you see how we can count the same set using 5*4C2?

 

[Steven G]

Interesting.

Let's take an example. With n=5, r=3, you have 3*5C3 = 3*10 = 30, and 5*4C2 = 5*6 = 30.

Looking for a way to see both sides as different ways to count the same things, I see that 3*5C3 is the number of ways to choose 3 of abcde and mark one as special (here, capitalized):

Abc Abd Abe Acd Ace Ade Bcd Bce Bde Cde
aBc aBd aBe aCd aCe aDe bCd bCe bDe cDe
abC abD abE acD acE adE bcD bcE bdE cdE

Do you see how we can count the same set using 5*4C2?

This is what I think is going on. The left side is saying that we can choose r people from n and then choose one of the chosen r to be say the president. The right hand side says you choose the president first and then from the remaining n-1 people we choose the remaining r-1 people.

Your example made it possible for me to easily see this. I don't know why I could not see this on my own. I guess my mathematical maturity was not enough.

As always I thank you for your time.

 

[Dr.Peterson]

This is what I think is going on. The left side is saying that we can choose r people from n and then choose one or the chosen r to be say the president. The right hand side says you choose the president first and then from the remaining n-1 people we choose the remaining r-1 people.

Your example made it possible for me to easily see this. I don't know why I could not see this on my own. I guess my mathematical maturity was not enough.

As always I thank you for your time.

I like combinatorial proofs like this (counting the same thing in two ways), so I knew immediately what sort of thing I expected to do. But I didn't fully see the proof myself until I worked through the example. I tell students at both high and low levels that "playing" with a problem using specific examples, making it more concrete or more familiar, often helps to get your mind around it. It works for me!

And your wording of the idea is very nice -- taking it from my concrete but dull specific numerical example to a more realistic and memorable (though generic) "example".

 

[Steven G]

I like combinatorial proofs like this (counting the same thing in two ways), so I knew immediately what sort of thing I expected to do. But I didn't fully see the proof myself until I worked through the example. I tell students at both high and low levels that "playing" with a problem using specific examples, making it more concrete or more familiar, often helps to get your mind around it. It works for me!

And your wording of the idea is very nice -- taking it from my concrete but dull specific numerical example to a more realistic and memorable (though generic) "example".

I have been looking at this identity a bit more and came up with what I think is a very nice proof.

Clearly nPr = n*(n-1)P(r-1). Also nCr = (nPr)/r!

So (nPr)/r! =n*((n-1)P(r-1)/(r(r-1)!)

Now nCr = (n/r)(n-1)P(r-1)/(r-1)! or nCr = (n/r)(n-1)C(r-1) or r(nCr) = n*(n-1)C(r-1).

I hope you like this!