4.2: Introduction to Counting

Probability relies on understanding what outcomes are possible and how many of them there are. But before we can study chance, we need to learn how to count correctly. This field is called combinatorics, and it helps us answer questions like:

• How many different ways can something happen?
• What changes when order does or does not matter?
• What do we do when we can't repeat selections?

Counting is not Probability

Counting doesn't tell us the likelihood of an event but only gives us the pieces we need to figure that out. Once we know how many outcomes are possible (and favorable), we can compute probability (we will see the approach in the next sections)

The multiplication rule of counting

Suppose we are curious about the total number of outcomes from flipping three coins in a row, while keeping track of the order. We list all possibilities below:

\[\{ HHH, HHT, HTH, HTT, THH, THT, TTH, TTT\}\]

Listing these out gives us a total of 8 possibilities. We figured this number from literal counting. However, what if we were interested in how many ways there are to flip 100 coins? That would take an extremely long time to count. So we devise mathematical methods to calculate counts without needing to sit and tally. Let's consider the 3-coin scenario again. Instead of listing all possible outcomes we can consider one flip at a time.

For the first flip, we have two possibilities; a Heads or a Tails. After one of those occurs, there are now two possibilities for the second flip. This means, for each of the two possibilities of the first flip, there are two possibilities for the second. We can easily see this when we write them out: HH, HT, TH and TT. We have a total of \(2\times 2 = 4\). However think about the third flip. For each of the 4 possible outcomes of the first two, there will be 2 more possibilities on the third flip. Therefore we can take \(4\times 2 = 8\) which matches out result from counting above.

This is called the multiplication rule of counting. It says that if we have \(n\) ways of one thing occurring, and \(m\) ways of another, there are \(n\times m\) ways they can happen together, assuming that the results of one way do not influence the other.

Now suppose we flip 100 coins. For each flip we multiply by 2. This leads to us needing to multiply by 2 over and over 100 times! However, we have notation for this, called exponents or powers.

\[ \text{number of outcomes } = 2\times 2\times 2\times \cdots \times 2 = 2^{100}\]

We can calculate that \(2^{100} = 1267650600228229401496703205376\). That's the total number of ways to flip 100 coins! Imagine counting to a number that large.

How secure is your PIN?

A more practical computation involves checking security of passwords and PINs (Personal Identification Numbers). A PIN consists of 4 digits which can take the 10 values between 0 and 9 (check by counting that there are 10 digits including 0)

In this case, instead of a coin flip, we have 10 possibilities for each digit. Our total number of possibilities is \(10\times10\times 10\times 10 = 10^4 = 10000\)

This is the total number of possible PINs, which means randomly guessing one would be very unlikely.

What if repetition is not allowed?

Suppose we wanted to assign labels to 5 objects as \(a\) through \(e\). The number of ways to do this is different from the previous examples. Let's consider the first item. We can label it \(a, b, c, d\) or \(e\) for a total of 5 possibilities. Let's say we decide to call it \(c\). We move on to the second object. However, this time, there are only 4 possibilities remaining: \(a, b, d\) or \(e\) since we've already used the label \(c\). Suppose we decide to call the second object \(a\). Moving on to the third, we now have 3 choices: \(b, d\) or \(e\). We call it \(e\). The fourth object can be labeled in two ways, either \(b\) or \(d\) and we pick \(d\). This means there is only 1 way to label the fifth object; it must be labeled \(b\).

We end up with the specific sequence \(c, a, e, d, b\). This is a particular way we could have labeled the objects, but how many total ways are there? Well, we appeal to the multiplication rule, but now have to consider that the number of ways to label decreases after each choice. There were 5 ways to label the first object, but once it is labeled there are only 4 ways for the second. This means there must be \(5\times 4 = 20\) ways just to label those first two. Continuing the pattern yields

\[\text{number of ways to label 5 items\} = 5\times 4\times 3\times 2\times 1 = 120\]

This type of pattern, where we start with a number and multiply by all whole numbers descending from it, is so common it has a specific name and symbol. We call it a factorial and write it as \(5!\) for example. We would pronounce that as "five factorial" and it would be equal to 120. Many scientific calculators are equipped with a factorial which can be typed with the exclamation point. In Microsoft Excel, factorials are done via the command =FACT()

Definition: Factorial

The factorial of a positive integer \( n \), written \( n! \), is the product of all positive integers less than or equal to \( n \).
Example: \( 6! = 6\times 5 \times 4 \times 3 \times 2 \times 1 = 720 \)

How many ways are there to shuffle a deck of cards?

A deck of playing cards consists of 52 standard cards and 2 jokers, usually omitted from play. If we shuffle the 52 standard cards, it is like randomly assigning them to an order. There are 52 possibilities for the top card, 51 for the card below it, 50 for the third card, and so on. We would have a total of \(52!\) possibilities. Evaluating this in a calculator gives an answer of \(8.0658\times 10^{67}\). This number is so large that it requires a special type of notation called scientific notation to write it out. In the number to the left, you can see we have a value 8.0658 which is being multiplied by \(10^{67}\). As we previously saw, this means 10 multiplied by itself 67 times. Each time we multiply by 10 we move the place value over by 1, changing where the decimal point is:

\[8.0658\times 10 = 80.658\]

As we do this more times we can simply count the decimal change:

\[8.0658 \times 10^3 = 8065.8\]

If we have more multiplications than digits we simply add trailing zeros.

\[8.0658\times 10^6 = 8065800\]

If we do this for the deck of cards we do this 67 times; can you see why we prefer scientific notation for large numbers?

\[8.0658\times 10^{67} = 80658000000000000000000000000000000000000000000000000000000000000000\]

Let this number sink in for a minute; it is the number of possible ways to shuffle a deck of cards. If we had every single person on early shuffle a deck of cards that would be about \(8000000000\) shuffles. That's not even going to make a dent in the total number of ways! In fact, there are so many ways to shuffle a deck, that if you do a perfect shuffle it is overwhelmingly likely that your specific card order has never been seen in the history of cards.

What if we use only part of the digits?

Let’s say we want to create a 3-digit ID from the numbers 0 through 5, with no repeats. We’d count:

\( 5 \times 4 \times 3 =\frac{5\times 4\times 3\times 2\times 1}{\2\times 1} = \frac{5!}{2!} \)

This is called a permutation, which is an arrangement of items where order matters.

Definition: Permutation

A permutation is an arrangement of objects where order matters. The number of permutations of \( r \) items from a group of \( n \) is:

\( P(n, r) = \frac{n!}{(n - r)!} \)

What if order doesn't matter?

Now imagine forming a 3-student committee from a class of 10 students. It doesn’t matter if Alex, Lee, and Jada are listed in a different order; it’s the same group.

This is where we use a combination. We calculate:

\( \frac{10 \times 9 \times 8}{3 \times 2 \times 1} = \frac{10!}{3!(10 - 3)!} = \binom{10}{3} \)

Definition: Combination

A combination is a selection of items where order does not matter. The number of combinations of \( r \) items from a group of \( n \) is:

\( C(n, r) = \binom{n}{r} = \frac{n!}{r!(n - r)!} \)

More examples

Let's look at another example of each case.

Case 1: Digits Can Repeat

A United States Social Security Number (SSN) has 10 positions. Each position can be filled by any digit from 0–9. That gives us 10 choices per digit:

10 × 10 × 10 × 10 × 10 × 10 × 10 × 10 × 10 × 10 = \( 10^{10} = 10,000,000,000 \)

This represents the number of SSNs possible if any digit can appear any number of times. This is a straightforward use of the multiplication rule.

Case 2: No Repeating Digits

Suppose we wish to add 10 items to a list. Each item will receive a number in the list, but they cannot be repeated.

We still have 10 positions, but one fewer option at each step:

10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = \( 10! = 3,628,800 \)

This use of factorials gives the number of ways to arrange 10 unique digits.

Case 3: Using Fewer Digits without Repeats

What if we only wanted to list out the top 4 items from 10 choices? There would only be 4 positions to fill, but 10 possibilities for the first one.

10 × 9 × 8 × 7 = \( \frac{10!}{(10 - 4)!} = \frac{10!}{6!} = 5040\)

This example was a permutation, a partial selection where order matters.

Case 4: Order Doesn't Matter

Finally, suppose you’re drawing a 4 raffle numbers and only care what the values are and not the order. This is a combination.

Using the use the combinations formula:

\( \binom{10}{4} = \frac{10!}{4!(10 - 4)!} = \frac{10!}{4!6!} = 210 \)

So out of 10 unique digits, there are 210 different ways to choose 4 of them when order doesn’t matter. That’s many fewer than with order!

Next Idea: Many problems in probability start by asking “What is the total number of possible outcomes?” We then divide the number of specific outcomes we are interested in to obtain their likelihood.

Summary

• Multiplication Rule: Use when steps are independent (e.g., 10 × 10 for repeated digits)
• Factorials: Represent total arrangements of n unique items
• Permutations: Order matters → \( \frac{n!}{(n - r)!} \)
• Combinations: Order doesn’t matter → \( \binom{n}{r} \)