**Combinations
**

A combination of *n* things taken* r* at a time is a subset of size *r* of a set of size *n.*

To denote the number of combinations of *n* things taken *r* at a time, we use the calculator symbols *n***C***r*. Other authors use the names
_{n}**C**_{r} or C(*n*, *r*).

*n***C***r* can be calculated by means of the number of permutations of *n* things
taken *r* at a time, or
*n***P***r* = (*n*)(*n* – 1) . . . (*n* – *r* + 1). For each
combination of size *r* there are *r*! permutations—arrangements of its
elements. So *n***C***r* = ^{nPr}**/**_{r!.}

Since *n***P***r* = ^{n!}**/**_{(n – r)!}

In fact, this is normally taken as the definition ofnCrcan be written as^{n!}/_{(r!)(n – r)!}

Definition:nCr=^{n! }/_{(r!)(n – r)!}

**Implications of the definition**

- The definition shows that
*n***C***r*=*n***C**(*n*–*r*). You might understand this as saying that the number of ways of choosing*r*out of*n*elements to be in a subset is the same as the number of ways of choosing the other*n*–*r*elements*not*to be in the subset. - The definition of
*n***C***r*also motivates the definition of 0! as 1, because*n***C***n*=*n***C**0 = 1: there's just one subset of all*n*elements.

**Calculating**

For calculating *n*C*r *by hand, using the expression ^{nPr}**/**_{r!} is usually
quicker than the definition. You can write out the numerator and
denominator and then cancel as much as possible in the larger terms on top.
For example, suppose you want to evaluate

11The 5 on the bottom reduces the 10 on top to a 2; the 4 and 2 on the bottom reduce the 8 to a 1; and the 3 on the bottom reduces the 9 to a 3. So you're left with (11)(2)(3)(7) = (11)(42) = 462.C5 =^{(11)(10)(9)(8)(7)}/_{(5)(4)(3)(2)}.

Many electronic calculators allow the calculation of *n***C***r* with the touch of
a few keys. Alternating multiplication and division avoids overflow in the
large numerators and keeps the intermediate result an integers. For
example, calculating 11**C**5 by

11/1*10/2*9/3*8/4*7/5

gives intermediate results of 11, 110, 55, 495, 165, 1320, 330, 2310, 462.

Reasoning about subsets of size *r*, from the point of view of a particular
element *x*, there are (*n* – 1)**C**(*r* – 1) combinations containing *x* and (*n* – 1)**C***r* combinations that don't contain *x*. So *n***C***r* = (*n* – 1)**C**(*r* – 1) + (*n* – 1)**C***r*. This result can be confirmed algebraically from the definition.

From this summation and the fact that 1**C**0 = 1**C**1 = 1, a table of combinations can be built up, beginning

1 1

1 2 1

1 3 3 1

1 4 6 4 1

This table is called *Pascal's triangle,* named after the seventeenth-century
mathematician and theologian Blaise Pascal who popularized it.

Copyright © 1999-2000 SciMathMN