Counting

Counting is the process of finding out how many elements are in a finite set of objects. It began with the study of games of chance, where probability calculations—like finding the chance of winning—rely on counting outcomes. When all outcomes are equally likely, the probability of an event is simply the ratio of favorable outcomes to the total number of possible outcomes. That’s why counting is a key skill in probability, but its uses go far beyond—it’s essential in many areas of mathematics.
When we count on our fingers, we’re handling small sets. This chapter will teach you how to count in sets that are way too big or complicated for finger-counting.

Basic Counting Principles

Method Modeling a random draw from a bag

A bag problem represents a random draw of balls from a bag. The bag contains $n$ balls, each numbered from 1 to $n$, which are indistinguishable by touch, making the draw random.

Bag with 4 ballsThere are two key criteria to distinguish these draws:

The order in which the balls are drawn. If order matters, it’s a "draw with order"; if not, it’s a "draw without order". For example, drawing balls 7, 33, and 24 is written as $(7,33,24)$ with order and $\{7,33,24\}$ without order. Note that $\{7,33,24\} = \{33,24,7\}$, but $(7,33,24) \neq (33,24,7)$.
Replacement. If each ball is placed back in the bag before the next draw, it’s a "draw with replacement"; if not, it’s a "draw without replacement".

Example

In a horse race with 10 horses, how many different ways can you bet on the top three finishers in exact order (triple forecast)? Model this as a draw from a bag.

Answer

This becomes: "How many ways can you draw 3 balls from a bag of 10 balls numbered from 1 to 10, with order and without replacement?"
For example, if the race results in horse number 3 finishing first, horse number 1 finishing second, and horse number 6 finishing third, this corresponds to drawing ball number 3 first, ball number 1 second, and ball number 6 third, written as $ (3,1,6) $.

Proposition Product rule

If there are $m$ different ways to do one thing, and for each of these, there are $n$ different ways to do another thing independently, the product rule says there are $m \times n$ ways to do both things in sequence.

Example

Three towns, $X$, $Y$, and $Z$, are connected by roads as shown. How many different ways can you travel from $X$ to $Z$ via $Y$?

Answer

For each of the 3 roads from $X$ to $Y$, there are 2 roads from $Y$ to $Z$. By the product rule, there are $3 \times 2 = 6$ different ways to travel from $X$ to $Z$ via $Y$.

Proposition Addition rule

The addition rule states that if you have $n$ ways to do one thing and $m$ ways to do another, and the two cannot be done at the same time, then there are $n + m$ total ways to choose one of the actions.

Example

A person is going shopping at one store today, either in the north or south part of town. In the north, they can shop at a mall, a furniture store, or a jewelry store (3 options). In the south, they can shop at a clothing store or a shoe store (2 options).
How many different stores can they choose from?

Answer

By the addition rule, there are $3 + 2 = 5$ different stores to choose from.

Factorials

Definition Factorial

For any positive integer $n$, $n!$ (read as "$n$ factorial") is the product of the first $n$ positive integers: $$n! = n \times (n-1) \times \dots \times 2 \times 1.$$ By convention, we define $0! = 1$.

Example

Calculate $4!$.

Answer

$\begin{aligned}[t]4! &= 4 \times 3 \times 2 \times 1\\ &= 24\end{aligned}$

Proposition

$$n(n-1)(n-2) \dots (n-p+1) = \frac{n!}{(n-p)!}$$

Proof

$$\begin{aligned}n(n-1)(n-2) \dots (n-p+1) &= \frac{n(n-1)(n-2) \dots (n-p+1)(n-p)(n-p-1) \dots 2 \times 1}{(n-p)(n-p-1) \dots 2 \times 1} \\ &= \frac{n!}{(n-p)!}\end{aligned}$$

Example

Express $10 \times 9 \times 8 \times 7$ in factorial form.

Answer

$$\begin{aligned}10 \times 9 \times 8 \times 7 &= \dfrac{10 \times 9 \times 8 \times 7 \times 6!}{6!} \\ &= \dfrac{10!}{6!} \end{aligned}$$

Definition Binomial Coefficient

For any integers $n \geqslant p \geqslant 0$, the binomial coefficient $\binom{n}{p}$ is defined as $$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Ordered Draws with Replacement (p-lists)

Definition p-list

A p-list is a selection of $p$ elements from a set of $n$ elements where the order of selection matters and elements can be repeated. It can be represented as an ordered p-tuple where components may be identical. This corresponds to drawing $p$ balls from a bag of $n$ balls with replacement and with order.

Example

The pair $(1,1)$ is a 2-list from the set $\{1,2,3\}$. Note that $(1,2)$ is a different 2-list from $(2,1)$ because the order is different. In total, there are 9 2-lists from this set, as shown in the tree diagram: $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(2,3)$, $(3,1)$, $(3,2)$, and $(3,3)$.

Proposition Number of p-lists

The number of p-lists of $p$ elements from a set of $n$ elements is given by the formula:$$n^p$$

Proof

For the first element in the list, there are $n$ choices. Since elements can be repeated (with replacement), there are also $n$ choices for the second element, and so on for all $p$ elements. By the product rule, the total number of lists is $n \times n \times \dots \times n$ ($p$ times), which is $n^p$.

Example

How many different 4-digit PINs can be created using the digits 0 through 9?

Answer

Each digit can be any of the 10 options, and repetition is allowed. This is a 4-list from a set of 10. The number of possible PINs is $10^4 = 10,000$.

Ordered Draws without Replacement (Arrangements)

Definition Arrangement

An arrangement is a selection of $p$ elements from a set of $n$ elements where the order of selection matters and elements cannot be repeated. It can be represented as an ordered p-tuple with distinct components. This corresponds to drawing $p$ balls from a bag of $n$ balls without replacement and with order.

Example

The pair $(1,3)$ is an arrangement of 2 elements from the set $\{1,2,3\}$. Note that $(3,1)$ is a different arrangement. In total, there are 6 arrangements of 2 elements from this set, as shown in the tree diagram: $(1,2)$, $(2,1)$, $(1,3)$, $(3,1)$, $(2,3)$, and $(3,2)$.

Proposition Number of Arrangements

The number of arrangements of $p$ elements from a set of $n$ elements is given by the formula:$$_nP_p = \frac{n!}{(n-p)!}$$

Proof

For the first element, there are $n$ choices. Since elements cannot be repeated, there are $n-1$ choices for the second, $n-2$ for the third, and so on, down to $n-p+1$ choices for the $p$-th element. By the product rule, the total number of arrangements is $n \times (n-1) \times \cdots \times (n-p+1) = \frac{n!}{(n-p)!}$.

Example

In a horse race with 10 horses, how many different ways can you bet on the top three finishers in exact order (triple forecast)?

Answer

This is an arrangement of 3 horses from 10. The number of ways is $_{10}P_3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720$.

Definition Permutation

A permutation is an arrangement of all $n$ elements of a set ($p=n$).

Example

The ordered triple $(1, 2, 3)$ is a permutation of the set $\{1, 2, 3\}$. In total, there are $3! = 6$ permutations of this set: $(1, 2, 3)$, $(1, 3, 2)$, $(2, 1, 3)$, $(2, 3, 1)$, $(3, 1, 2)$, and $(3, 2, 1)$.

Proposition Number of Permutations

The number of permutations of a set of $n$ elements is $_nP_n = n!$.

Proof

This follows directly from the arrangement formula by setting $p=n$:$_nP_n = \frac{n!}{(n-n)!} = \frac{n!}{0!} = n!$.

Example

How many ways are there to seat 100 guests at 100 chairs for a wedding?

Answer

This is the number of permutations of 100 guests, which is $100! \approx 9.33 \times 10^{157}$.

Unordered Draws without Replacement (Combinations)

Definition Combination

A combination is a selection of $p$ elements from a set of $n$ elements where the order of selection does not matter. It can be represented as a subset of $p$ elements. This corresponds to drawing $p$ balls from a bag of $n$ balls without replacement and without order.

Example

The set $\{1,3\}$ is a combination of 2 elements from the set $\{1,2,3\}$. Note that $\{3,1\}$ is the same combination. In total, there are 3 combinations of 2 elements from this set: $\{1,2\}$, $\{1,3\}$, and $\{2,3\}$. Each combination corresponds to $2! = 2$ arrangements.

Proposition Number of Combinations

The number of combinations of $p$ elements from a set of $n$ is given by the binomial coefficient:$$\binom{n}{p} = \frac{n!}{p!(n-p)!}$$

Proof

For any combination of $p$ elements, there are $p!$ ways to arrange them. Therefore, the number of arrangements ($_nP_p$) is equal to the number of combinations ($\binom{n}{p}$) multiplied by $p!$.$$_nP_p = \binom{n}{p} \times p! \implies \frac{n!}{(n-p)!} = \binom{n}{p} \times p!$$Dividing by $p!$ gives the formula for combinations.

Example

How many different ways are there to choose 5 numbers for a Lotto draw from 49 numbers?

Answer

The order of the numbers does not matter, so this is a combination. The number of ways is $\binom{49}{5} = 1,906,884$.

Summary of Counting Formulas

This table summarizes the formulas for selecting $p$ elements from a set of $n$ elements.

	With Replacement	Without Replacement
Order Matters (p-list/Arrangement)	$n^p$	$_nP_p = \dfrac{n!}{(n-p)!}$
Order Does Not Matter (Combination)	$\binom{n+p-1}{p}$	$\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$

Applications to Probability

The primary motivation for developing the techniques of counting was to solve problems in probability. For an experiment where all outcomes are equally likely, the probability of an event $E$ is defined by the ratio of the number of favorable outcomes to the total number of possible outcomes.

Method Solving a Probability Problem with Counting

To find the probability of an event, follow these steps:

Identify the experiment: Determine what random process is taking place (e.g., drawing cards, rolling dice, selecting people).
Model the outcomes: Determine if the selection involves order and/or replacement. This will determine which counting formula to use.
Calculate the total number of outcomes ($\Card{U}$): Use the appropriate formula from the summary table to find the size of the sample space.
Calculate the number of favorable outcomes ($\Card{E}$): Define the event of interest and use the counting rules to find its size.
Calculate the probability: Apply the equiprobability formula, $P(E) = \frac{\Card{E}}{\Card{U}}$.

Example

In a horse race with 10 horses, you bet on the top three finishers in exact order (a triple forecast, or "tiercé"). If you place one bet, what is the probability of winning?

Answer

Let's apply the 5-step method for solving probability problems with counting.

Identify the experiment: A race is run with 10 horses, and the event of interest is the ordered result of the top three finishers.
Model the outcomes: We are selecting 3 horses from 10. Since the finishing order is exact, order matters. A horse cannot finish in more than one position, so this is without replacement. The model is an arrangement.
Calculate the total number of outcomes ($\Card{U}$): The total number of possible top-three finishes is the number of arrangements of 3 horses from a set of 10.$$ \Card{U} = {}_{10}P_3 = \frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720 $$There are 720 possible outcomes for the top three positions.
Calculate the number of favorable outcomes ($\Card{E}$): To win, your bet must match the single correct finishing order. Therefore, there is only one favorable outcome.$$ \Card{E} = 1 $$
Calculate the probability: Using the equiprobability formula:$$ P(\text{Win}) = \frac{\Card{E}}{\Card{U}} = \frac{1}{720} $$

The probability of winning with a single bet is 1 in 720.