Combinatorics and computing

9.5 Combinations


In Section 9.4, we investigated the problem of selecting a certain number of items from a set, where the order in which the items are selected is taken into account. A more common problem in practice is to ascertain the number of ways in which a selection can be made, without distinguishing between different orders. Problems of this kind are called combinations problems.
For example, suppose that the rules of a lottery specify that entrants must select eight different numbers chosen from the natural numbers from 1 to 45 inclusive. In how many different ways can this selection be made?


As a first step towards solving the problem, we can calculate the number of choices if order is taken into account; it is ⁴⁵P₈ . This number is not the answer to the problem, of course, because we have counted the same selection many times, once for each different way in which the eight numbers can be arranged. In fact, we can state precisely how much too large it is; since there are 8! ways of arranging the eight chosen numbers, ⁴⁵P₈ is too large by a factor of 8!. The correct answer to the problem is therefore ⁴⁵P₈ / 8!, which equals 215 553 195.
This example gives us a clue to the solution of the combinations problem in general. Suppose we want to select r items without replacement from a set of n items, without taking into account the order in which the selection is made. (In the language of sets, we want to choose a subset with r elements from a set with n elements.) In how many ways can this be done?
The number of selections with order taken into account is ⁿPr. Now, if order is not to be taken into account, then this number is too large by a factor of r!, because r! is the number of permutations of the r selected elements. The correct answer is therefore ⁿP_r / r! . Using the fact that

we obtain the following expression as the answer:

This expression is denoted by or ⁿC_r . It is the number of ways that r items can be chosen from a set of n items. Equivalently, it is the number of r-element subsets of an n-element set. Given a particular value of n, the values of (as r ranges from 0 to n) are referred to as the nth binomial coefficients, because they occur in the binomial theorem in algebra.
Using the alternative expression for ⁿP_r , we obtain another expression for that is generally more useful for computations: