Associated Topics || Dr. Math Home || Search Dr. Math

### 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.

```

```
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/
```
Associated Topics:
High School Permutations and Combinations

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search