Combinatorics BasicsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/