Combinatorics Basics

Date: 07/07/97 at 21:04:27
From: Randy Scamacca
Subject: Combinatorics

I need to prove that n chooses n-1 = n;  e.g. C(n,n-1) = n.

I know that it is true, e.g. 10:9 = 10, but I don't know how to prove 
it.  Our professor asked us to seek the proof on the Web, but I can 
not find it.

Thanks for any help you can give.

Date: 07/08/97 at 07:24:59
From: Doctor Anthony
Subject: Re: Combinatorics

The usual way to prove the expression for nCr, that is, the number of 
ways of choosing r things from n things, is first to prove the 
expression for nPr, that is, the number of PERMUTATIONS of r things 
that can be made from n things.

If we have say 10 different letters and we are asked how many 
arrangements of 4 letters can be made from these 10, then it is easy 
to see that we could pick the first letter in 10 ways, the second 
letter in 9 ways, the third letter in 8 ways, and the fourth letter 
in 7 ways, giving a total number of different arrangements equal to  
10 x 9 x 8 x 7 = 5040 ways.

Thus  10P4 = 5040
                                                      10!
We could use factorial notation to get this result   -----  =  5040
                                                       6!

                                          10 x 9 x 8 x 7 x 6!    10!
This result is obvious since we multiply  -------------------  = ---
                                                  6!              6!
                            n!
In the general case nPr =  ----
                          (n-r)!

We now go on to find an expression for the number of COMBINATIONS of 
4 things that could be made from 10 things.  We call this number 10C4.

We saw that the total number of permutations of 4 things from 10 was 
equal to 5040 = 10P4. We could get this result by first taking each 
group of 4 letters - there are 10C4 such groups - and finding every 
arrangement of those 4 letters.  Clearly 4 letters can be arranged in 
4! ways = 24 ways, so the total number of permutations of 4 letters 
taken from 10 is the number of combinations of 4 things taken from 
10 multiplied by 4!

That is: 10C4 x 4! =  10P4

                      10P4         10!
              10C4 = -------  =  --------
                       4!         6! 4!

In the general case with r things taken from n things we get:

                  n!
        nCr  = -------
               (n-r)! r!


In the case where r = n-1 we get same result as for r = 1

                    n!                 n!
      nC(n-1) = --------------   = ----------   =  n
                (n-n+1)!(n-1)!      1! (n-1)!      

                 n!
      nC1  =  --------   = n 
             (n-1)! 1! 

It is clear that we can swap r and n-r in the expression without 
changing the value of nCr. So 10C4 = 10C6, 10C3 = 10C7, 10C2 = 10C8,  
etc. 

These nCr values are found in Pascal's triangle as the coefficient of 
x^r in the expansion of (1+x)^n, and as you may know, the coefficient 
of x^r is always the same as that of x^(n-r), that is, the rows of 
Pascal's triangle are symmetrical about the middle.

-Doctor Anthony,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/