10  Counting Rules

Now that we have established the definition of probability, the next step is to determine how to count the number of possible outcomes in a structured way.

In many probability problems, we need to calculate the likelihood of an event occurring based on the number of favorable outcomes relative to the total number of possible outcomes. However, when dealing with large or complex sample spaces, manually listing all possible outcomes is impractical.

To efficiently compute probabilities, we rely on counting rules from combinatorics, which provide systematic methods to count possible outcomes. These include (see Chapter 2):

10.1 With/Without Replacement? Order Matters or Not?

One key distinction in counting problems is whether selection is with or without replacement.

  • If a ball is drawn from an urn and returned before the next draw, then every selection remains independent, and the number of available choices does not change. This is known as drawing with replacement. For example, if an urn contains six balls, each ball has a \(1/6\) probability of being chosen, and this probability remains the same for every draw.

  • In contrast, drawing without replacement means that once a ball is selected, it is not returned to the urn. This affects the probability of subsequent draws. A common example is a lottery draw, where seven winning numbers are selected from a total of 35 balls. Since each number can only appear once, this is an example of drawing without replacement.

Another important factor is whether the order of selection matters when counting possibilities.

  • In some cases, order does matter. For example, imagine that a company requires employees to create five-letter security codes using the letters A, B, C, D, and E. Here the order of the letters celarly matters since password ABCDE is different from password ACBDE. This means the number of possible passwords availbale to choose from is determined by permutations, where order plays a role.

  • In other cases, order does not matter. Returning to the lottery example, suppose the machine selects the balls in the order 1,2,3,4,5,6,7. This sequence represents the same lottery result as if the balls had been drawn in the order 7,6,5,4,3,2,1. Since the order of selection does not change the outcome, this scenario follows combinations, where only the chosen numbers matter, not their sequence.

By understanding whether we are dealing with replacement or no replacement and ordered or unordered selection, we can use combinatorial techniques to systematically count possible outcomes in probability problems.

10.1.1 Drawing with Replacement, Order Matters

Example 9.3: PIN Code Generation

Consider a four-digit PIN code, where each digit can be any number from 0 to 9. Since each digit is chosen independently and can be repeated, every unique sequence forms a distinct PIN code.

This is an example of permutations with repetition, where the total number of possible PIN codes is given by: \[N^n\] where:

  • \(N\) is the number of available choices for each digit (10 digits: 0–9).
  • \(n\) is the number of digits in the PIN code (4-digit code). Applying the formula: \[10^4 = 10,000 \]

This means there are 10,000 unique PIN codes that can be generated under these conditions.

Example 9.4: Vehicle Registration Numbers in Sweden

How many possible vehicle registration numbers exist in Sweden? In Swedish license plates, a registration number consists of three letters followed by three digits. Since letters and digits can be repeated, this follows the rule of permutations with repetition.

To calculate the total number of possible license plates, we consider:

  • The first three characters are letters, chosen from 26 available options.
  • The last three characters are digits, chosen from 10 available options (0–9).

Using the multiplication principle, the total number of possible registration numbers is:

\[ 26 \times 26 \times 26 \times 10 \times 10 \times 10 = 26^3 \times 10^3 = 17,576,000 \]

This means that Sweden can issue up to 17.58 million unique vehicle registration numbers under this system. The formaula is generally written as \(N_1^{n_1} \times N_2^{n_2}\) where:

  • \(N_1 = 26\) (number of available letters), \(n_1 = 3\) (three letters chosen).
  • \(N_2 = 10\) (number of available digits), \(n_2 = 3\) (three digits chosen).

10.1.2 Drawing with Replacement, Ignoring Order

Example 9.5: Selecting Ice Cream Flavors 🍦

Imagine an ice cream shop that offers six different flavors. A customer selects three scoops of ice cream, where:

  • The same flavor can be chosen multiple times (replacement).
  • The order of the scoops does not matter— choosing (vanilla, chocolate, vanilla) is the same as (chocolate, vanilla, vanilla).

Since order is ignored, but repetition is allowed, we calculate the number of possible selections using combinations with replacement, given by the formula: \[\binom{N + n - 1}{n} = \frac{(N + n - 1)!}{n!(N - 1)!} \]

where:

  • \(N = 6\) (number of available flavors).
  • \(n = 3\) (number of scoops selected).

Applying the formula:

\[ \binom{6+3-1}{3} = \binom{8}{3} = \frac{8!}{3!(5!)} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \]

Thus, there are 56 different ways to choose three scoops of ice cream when order does not matter, but flavors can be repeated.

10.1.3 Drawing without Replacement, Order Matters

Example 9.6: Finalist Selection in ESC 🎤🎶

In the semi-final rounds of the Eurovision Song Contest, five countries have reached the last stage. The final ranking must be determined, where each country is assigned a unique position from 1st place to 5th place.

Since the order of ranking is important, we need to determine how many different ways the top five positions can be arranged. This follows the permutation rule, as once a country’s submission is assigned a position, it cannot be placed elsewhere. The total number of possible rankings is calculated as: \[5 \times 4 \times 3 \times 2 \times 1 = 5! = 120 \]
Thus, there are 120 possible ways to assign the final rankings to the five finalists.

This follows the principle of permutations without replacement, meaning that each finalist is placed in a unique ranking, and no two countries can hold the same position.

10.1.4 Drawing without Replacement, Ignoring Order

Example 9.7: Poker Hands 🎴

In a standard game of five-card poker, a player is dealt five random cards from a standard deck of 52 playing cards. Since:

  • The order of the cards does not matter (a hand with A♠ K♠ Q♠ J♠ 10♠ is the same regardless of the order drawn).

  • Cards are drawn without replacement (once a card is drawn, it cannot be selected again), we calculate the total number of different poker hands using combinations without replacement: \[\binom{52}{5} = \frac{52!}{(52-5)!5!} = \frac{52 \times 51 \times 50 \times 49 \times 48}{5!} = 2 598 960 \]
    Thus, there are 2 598 960 unique five-card poker hands in a standard deck.

What is the probability of getting a flush on the first draw?

A flush in poker means that all five cards in the hand belong to the same suit (♠, ♥, ♦, or ♣). We define event \(A\) as the event of being dealt a flush directly, meaning that all five cards in the hand belong to the same suit (♠, ♥, ♦, or ♣).

To compute the probability \(A\), consider that:

  • If we focus on only hearts, there are 13 hearts in the deck, and we need to choose 5 of them: \[\binom{13}{5} = \frac{13!}{(13-5)!5!} = 1287 \]

  • The same calculation applies for the other three suits (spades, diamonds, and clubs), so the total number of flush hands is: \[4 \times 1287 = 5148 \]

Since all poker hands are equally likely, the probability of being dealt a flush is: \[P(A) = \frac{5148}{2598960} \approx 0.00198\]
This means that the probability of being dealt a flush on the first draw is approximately 0.198%.

Exercises

  1. A full house in poker consists of three cards of one rank and two cards of another (e.g., Q♠ Q♥ Q♦ 7♣ 7♦). What is the probability of getting a full house on the first draw?

Since the order does not matter, and cards are drawn without replacement, we use combinations to determine the number of possible full house hands.

Selecting one of 13 ranks for the three-of-a-kind: \(\binom{13}{1} = 13\). Choosing three suits out of four for that rank: \(\binom{4}{3} = 4\).

Total ways to select the three-of-a-kind: \[13 \times 4 = 52 \]

Selecting one of 12 remaining ranks for the pair: \(\binom{12}{1} = 12\). Choosing two suits out of four for that rank: \(\binom{4}{2} = 6\). Total ways to select the pair: \[12 \times 6 = 72 \]

Multiplying both parts together we get: \[52 \times 72 = 3 744 \]
Thus, there are 3 744 unique full house hands in a standard deck.

Since we already know that there are 2 598 960 total poker hands, the probability of being dealt a full house is (defined as event \(A\)):

\[P(A) = \frac{3744}{2598960} \approx 0.00144\]

This means the probability of being dealt a full house on the first draw is 0.144%.

  1. A teacher randomly arranges 6 students in a line for a class photo. Each student is assigned a unique position.
  1. How many different ways can the 6 students be arranged in a line?
  2. What is the probability that a specific student (A) is in the first position?
  3. What is the probability that student A is first and student B is second in the lineup?

  1. There are \(P(6,6) = 6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\) different ways to arrange the students in a line (see Chapter 2 exercises for more details)

  2. Since all arrangements are equally likely, student A can be in any of the 6 positions. If we fix A in the first position, the remaining 5 students can be arranged freely: \[5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\]
    The probability of A being first is then given by \[P(A) = \frac{120}{720} = \frac{1}{6} \approx 0.167 \text{ (16.7\%)}\]

  3. If A is fixed in the first position, there are 5 students remaining. If B is fixed in the second position, there are 4 students left to be arranged: \[4! = 4 \times 3 \times 2 \times 1 = 24\]
    The probability of A being first and B being second is then given by: \[P(B) = \frac{24}{720} = \frac{1}{30} \approx 0.0333 \text{ (3.33\%)}\]