Systematic Listing Strategies

The Fundamental Counting Principle

When calculating the total number of possibilities for a sequence of independent choices, we use systematic listing. This is often formalised as the product rule: if task one can be done in $m$ ways and task two can be done in $n$ ways, the total number of ways to complete both tasks in order is $m \times n$ ways. This logic extends to any number of tasks performed in succession.

Systematic Listing for Codes

Consider a security code consisting of 4 digits, where each digit is an integer between 0 and 9 inclusive. This means there are 10 possibilities for each individual position.

How many different codes are possible?

Because there are 10 choices for the first digit, 10 for the second, 10 for the third, and 10 for the fourth, we calculate:

$10 \times 10 \times 10 \times 10 = 10000$

This result is logical because there are exactly 10,000 unique numbers in the range from 0000 to 9999.

How many possible codes are there where each digit is different?

In this scenario, once a digit is used, it cannot be used again.

1. For the first digit, there are 10 choices.
2. For the second digit, there are 9 remaining choices (any digit except the one used first).
3. For the third digit, there are 8 choices (any digit except the first or second).
4. For the fourth digit, there are 7 choices remaining.

The calculation is: $10 \times 9 \times 8 \times 7 = 5040$.

How many codes have exactly two adjacent digits the same and two unique digits?

This requires identifying the possible positions for the repeated digit. There are three possible arrangements:

1. The 1st and 2nd digits are the same.
2. The 2nd and 3rd digits are the same.
3. The 3rd and 4th digits are the same.

To find the number of ways to choose the digits, we have 10 choices for the digit that will be repeated, 9 choices for the first unique digit, and 8 choices for the second unique digit. This gives $10 \times 9 \times 8$. Since this can occur in any of the three positions mentioned above, the total is:

$3 \times (10 \times 9 \times 8) = 2160$.

How many codes have at least two digits the same?

Instead of counting every combination of two, three, or four repeated digits, it is more efficient to use the complement method. We subtract the number of codes where all digits are different from the total number of possible codes:

$10000 - 5040 = 4960$.

Example: Outfit Combinations

Martha has 4 jumpers, 5 pairs of trousers, and 3 pairs of trainers. To find the total number of different outfit combinations she can make, we multiply the number of options for each item of clothing:

$4 \times 5 \times 3 = 60$.

Application to Licence Plate Systems

A new licence plate system uses two letters followed by up to 4 digits (0 to 9).

Exactly 4 digits

If we assume all 26 letters are allowable and there are 10 possibilities for each digit, a plate with two letters and exactly 4 digits has:

$26 \times 26 \times 10 \times 10 \times 10 \times 10 = 6760000$ possibilities.

Exactly 4 digits, but letters cannot be the same

If the two letters must be distinct, there are 26 choices for the first letter and 25 for the second:

$26 \times 25 \times 10 \times 10 \times 10 \times 10 = 6500000$.

Exactly 4 digits, no letters the same and no digits repeated

Applying the restriction to both letters and digits:

$26 \times 25 \times 10 \times 9 \times 8 \times 7 = 3276000$.

Two letters and up to 4 digits

In cases where there can be 1, 2, 3, or 4 digits (with at least 1 digit required), we must sum the totals for each possible length. Note that in this context, 01 is treated as different from 1.

1. One digit: $26 \times 26 \times 10 = 6760$
2. Two digits: $26 \times 26 \times 10 \times 10 = 67600$
3. Three digits: $26 \times 26 \times 10 \times 10 \times 10 = 676000$
4. Four digits: $26 \times 26 \times 10 \times 10 \times 10 \times 10 = 6760000$

Total number of possibilities: $6760000 + 676000 + 67600 + 6760 = 7510360$.