Understanding Binomial Coefficients: n Choose r

[2^Oscar]

Hey guys,

I've been reading up on binomial coefficients and I have found a brief section on n choose r. I understand vaguely what it actually is, however in my textbook there is a step by step proof of how we show that:


( \stackrel{n}{r} ) = \frac{n!}{r!(n-r)!}


I can follow where this comes from. My book states that S={1,2...n} and then proceeds to prove the above in three steps; firstly by choosing an r-element subset (called T) of S where there are ( \stackrel{n}{r} ) choices. Secondly choosing an arrangement of T where there will be r! choices. Finally by choosing an arrangement of the remaining n-r elements of S where there are (n-r)! choices. By the multiplication principle the total number of arrangements of S (i.e. n!) is equal to the product of all these three. Then you simply rearrange your result to get the above.

Could someone please explain to me the second and third steps of this because I'm really struggling to see how these combined with step one would give the number of arrangements of S.


Cheers,
Oscar

 

[HallsofIvy]

Well, here's a different way of saying the same thing. "n choose r" means that you have a set of n objects and you are choosing r of those objects. How many ways can you do that? One method is this: imagine that you have all n objects in a row before you. Write, below each one "Y" if you are choosing it, "N" if not. Now you have n letters, r of them "Y" and n-r of them "N".

How many different ways are there of ordering (or writing) a word consisting of r "Y"s and n-r "N"s? Okay, now imagine labeling each of the "Y"s "1", "2", ..., "r" and each of the n-r "N"s "1", "2", ..., "n-r" so that they are all different. How many ways can you order n different symbols? Of course, you have n choices for the first, then, having chosen that, n-1 symbols are left so you have n-1 choices for the second, then n-2 for the third, etc. There are n(n-1)(n-1)...(3)(2)(1)= n! ways to do that.

But, of course, the "Y"s are NOT all different. For anyone of those n! arrangements, we could swap two "Y"s and not change it. How many different ways are there to swap just the "Y"s? Since there are r "Y"s there are r! ways to do that. That is, every arrangement with the identical "Y"s has been counted r times. To find the actual number of ways of arranging those letters, we have to divide by r! to allow for the rearrangements of just the "Y"s. Similarly, because there are n-r identical "N"s, we have to divide by (n-r)! to allow for that: altogether, the number of ways to arrange n objects, n of them identical and the other n-r also identical is
\frac{n!}{r!(n-r)!}

 

[2^Oscar]

Thank you very much for your reply - apologies for not replying myself sooner.

I see exactly what you mean now, part of what helped was reading the next chapter about multinomial coefficients; it helps put things in perspective.

Thanks again,
Oscar