Combinatorics and computing

Example 9.5.1 A test is to be generated by selecting six questions from a test bank consisting of 50 questions. How many different tests are possible, assuming that the order in which the questions appear on the test is not taken into account?


Solution The number of different tests is:
A comment about evaluating these kinds of expressions on a calculator is appropriate here. Some calculators have keys for evaluating ⁿP_r and directly. If a calculator with these facilities is not available, it may be necessary first to perform some simple cancellations by hand, in order to avoid overflow problems on the calculator. (In Example 9.5.1, the 48 in the numerator cancels with the factors 6, 4 and 2 in the denominator, and the 45 in the numerator can be divided by the 5 and the 3 in the denominator, leaving the expression 50 × 49 × 47 × 46 × 3 to be evaluated on a calculator.)


Example 9.5.2 A task group consisting of three women and three men is to be chosen from the members of an organisation consisting of 23 women and 18 men. In how many ways can this be done?


Solution The three women can be chosen in ways. For each of these choices, the three men can be chosen in ways. By the Multiplication principle, the total number of ways is





In some problems, combinations appear in a rather more subtle way, as the next example illustrates.


Example 9.5.3 A motorist wants to travel from A to B using the grid of streets shown in Figure 9.2. Assuming that no ‘doubling back’ is allowed at any stage of the journey, in how many ways can this be done?