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 nCr 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! permutationsarrangements 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
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
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)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.
From this summation and the fact that 1C0 = 1C1 = 1, a table of combinations can be built up, beginning
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