Systematic Listing Strategies

The Fundamental Multiplication Principle

When we need to find the total number of combinations for a series of tasks, we use the multiplication principle. This states that if task A can be done in $m$ ways and task B can be done in $n$ ways, the number of ways to perform A then B is simply $m \times n$. This logic extends to any number of tasks. For example, if you have $p$ ways to do a third task, the total combinations are $m \times n \times p$.

Systematic Listing for Codes

Consider a code consisting of 4 digits, where each digit is an integer between 0 and 9 inclusive. We can determine various counts based on specific constraints:

1. Total possible codes: Since there are 10 choices (0 to 9) for each of the four positions, the total is $10 \times 10 \times 10 \times 10 = 10,000$. This matches the number of integers between 0000 and 9999.

2. Codes with unique digits: For the first digit, there are 10 choices. For the second, only 9 remain (as it must differ from the first). For the third, 8 choices remain, and for the fourth, 7 choices. The total is $10 \times 9 \times 8 \times 7 = 5,040$.

3. Codes with exactly two adjacent identical digits and two unique digits: There are three possible positions for the repeated pair: positions 1 and 2, positions 2 and 3, or positions 3 and 4. We choose the digit to be repeated (10 choices) and then the two unique digits for the remaining slots ($9 \times 8$ choices). Since there are three possible configurations, the total is $3 \times (10 \times 9 \times 8) = 2,160$.

4. Codes with at least two identical digits: It is often easier to use subtraction from the total. The number of codes with at least one repetition is the total number of codes minus the number of codes where every digit is unique: $10,000 - 5,040 = 4,960$.

Example: Combinations of Outfits

Martha has 4 jumpers, 5 pairs of trousers, and 3 pairs of trainers. To find the total number of unique outfit combinations, we multiply the number of choices for each category: $4 \times 5 \times 3 = 60$ different outfits.

Licence Plate Systems

Listing strategies are frequently applied to registration or licence plate problems. Suppose a system uses two letters followed by up to 4 digits (0 to 9).

Scenario A: Exactly 4 digits There are 26 possibilities for each of the two letters and 10 for each of the four digits: $26 \times 26 \times 10 \times 10 \times 10 \times 10 = 6,760,000$.

Scenario B: Exactly 4 digits, but letters must be different The first letter has 26 choices, while the second has only 25: $26 \times 25 \times 10 \times 10 \times 10 \times 10 = 6,500,000$.

Scenario C: Exactly 4 digits, letters different, and no digits repeated We combine the letter constraint with the unique digit constraint ($10 \times 9 \times 8 \times 7$): $26 \times 25 \times 10 \times 9 \times 8 \times 7 = 3,276,000$.

Scenario D: Two letters and up to 4 digits (at least 1 digit) In this case, we must sum the possibilities for plates having 1, 2, 3, and 4 digits separately:

• One digit: $26 \times 26 \times 10 = 6,760$
• Two digits: $26 \times 26 \times 10 \times 10 = 67,600$
• Three digits: $26 \times 26 \times 10 \times 10 \times 10 = 676,000$
• Four digits: $26 \times 26 \times 10 \times 10 \times 10 \times 10 = 6,760,000$ Total: $6,760,000 + 676,000 + 67,600 + 6,760 = 7,510,360$.