- #1
2^Oscar
- 45
- 0
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:
( [tex]\stackrel{n}{r}[/tex] ) = [tex]\frac{n!}{r!(n-r)!}[/tex]
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 ( [tex]\stackrel{n}{r}[/tex] ) 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
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:
( [tex]\stackrel{n}{r}[/tex] ) = [tex]\frac{n!}{r!(n-r)!}[/tex]
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 ( [tex]\stackrel{n}{r}[/tex] ) 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