MATtours of discrete mathematics

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 nCr. Other authors use the names _nC_r or C(n, r).

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

Since nPr = ^n!/_(n – r)!

nCr can be written as ^n!/_{(r!)(n – r)!}

In fact, this is normally taken as the definition of nCr.

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

Implications of the definition

The definition shows that nCr = nC(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 nCr also motivates the definition of 0! as 1, because nCn = nC0 = 1: there's just one subset of all n elements.

Calculating

For calculating nCr 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

11C5 = ^{(11)(10)(9)(8)(7)}/_(5)(4)(3)(2).

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

Many electronic calculators allow the calculation of nCr 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 11C5 by
11/1*10/2*9/3*8/4*7/5
gives intermediate results of 11, 110, 55, 495, 165, 1320, 330, 2310, 462.

Summation

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)Cr combinations that don't contain x. So nCr = (n – 1)C(r – 1) + (n – 1)Cr. This result can be confirmed algebraically from the definition.

Pascal's triangle

From this summation and the fact that 1C0 = 1C1 = 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.