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.

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 $n$,, 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 says: if you have $n$ ways to do one thing and $m$ ways to do another thing, and you can’t do both at the same time, then the total number of ways to do either one is $n + m$.

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.$$ We also define $0! = 1$.

Example

Calculate $4!$.

Answer

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

Definition Number of Arrangements

Let $ n $ and $ p $ be positive integers such that $ n > p \geqslant 1 $.
The number of arrangements of $ p $ elements chosen from $ n $, is given by:$$\frac{n!}{(n-p)!}$$

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 > p \geqslant 0$, the binomial coefficient $\binom{n}{p}$ is defined as $\binom{n}{p} = \frac{n!}{p!(n-p)!}$.

Ordered Draws with Replacement

Proposition Ordered Draws with Replacement

The number of different ways to draw $p$ balls from a bag of $n$ balls with replacement and with order is $n^p$.

Proof

For the first draw, you have $n$ choices. Since it’s with replacement, you have $n$ choices again for the second draw, and so on, for all $p$ draws. Following the product principle, the total number of ways is $n \times n \times \dots \times n$ (p times), which is $n^p$.

Example

How many different ways are there to draw 2 balls from a bag of 3 balls with replacement and with order?

Answer

The number of ways is $3^2 = 9$.

Tree diagram of drawing 2 balls with order and with replacement from a bag of 3 balls.

Ordered Draws without Replacement

Proposition Ordered Draws without Replacement

The number of different ways to draw $p$ balls from a bag of $n$ balls without replacement and with order (where $p \leq n$) is the number of arrangements, $\frac{n!}{(n-p)!}$.

Proof

Imagine you have a bag with $n$ distinct balls, and you want to draw $p$ balls one by one without putting them back (without replacement), while keeping track of the order in which you draw them (with order).

First draw: Start with the bag, which has $n$ balls. For the first draw, you can pick any of these $n$ balls. So, there are $n$ possible choices for the first position in your sequence.
Second draw: After drawing the first ball and not putting it back, only $n-1$ balls are left in the bag. For the second draw, you can choose any of these $n-1$ balls. So, there are $n-1$ choices for the second position.
Third draw: After drawing the second ball, $n-2$ balls remain. For the third draw, you have $n-2$ choices for the third position.
Continuing the process: This pattern keeps going for each draw. For the fourth draw, there are $n-3$ choices, then $n-4$ for the fifth, and so on, until you reach the $p$-th draw.
$p$-th draw: By the time you draw the $p$-th ball, you’ve already drawn $p-1$ balls, leaving $n - (p-1) = n - p + 1$ balls in the bag. So, for the $p$-th draw, there are $n - p + 1$ choices for the $p$-th position.

Using the multiplication principle, we multiply the number of options for each draw:$$n \times (n-1) \times (n-2) \times \cdots \times (n-p+1)$$To express this in terms of factorials, notice that:$$\begin{aligned}[t]n \times (n-1) \times (n-2) \times \cdots \times (n-p+1)&=\frac{n \times (n-1) \times (n-2) \times \cdots \times (n-p+1) \times \textcolor{olive}{(n-p) \times (n-p-1) \times \cdots \times 2 \times 1}}{\textcolor{olive}{(n-p) \times (n-p-1) \times \cdots \times 2 \times 1}}\\&= \frac{n!}{(n-p)!}\end{aligned}$$This confirms the result.

Example

How many different ways are there to draw 2 balls from a bag of 3 balls without replacement and with order?

Answer

The number of ways is $\frac{3!}{(3-2)!} = 3 \times 2 = 6$.

Tree diagram of drawing 2 balls with order and without replacement from a bag of 3 balls.

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 corresponds to drawing 3 balls from a bag of 10 with order and without replacement. The number of ways is $\frac{10!}{(10-3)!} = 10 \times 9 \times 8 = 720$.

Corollary Permutations

The number of ways to arrange all $n$ balls from a bag without replacement and with order is $n!$.

Corollary Permutations

The number of ways to arrange all $n$ balls from a bag without replacement and with order is $n!$.

Proof

Proof 1: we draw all $n$ balls from a bag of $n$ distinct balls without replacement and with order (we draw every ball in the bag).Substitute $p = n$ into the proposition’s formula:$$\begin{aligned}\frac{n!}{(n-p)!} &= \frac{n!}{(n-n)!}\\ &= \frac{n!}{0!}\\ &=\frac{n!}{1}&& (\text{by definition, } 0! = 1)\\ &= n!\end{aligned}$$Thus, the number of different ways to draw all $n$ balls from the bag without replacement and with order is $n!$.
Proof 2: Consider a bag containing $n$ distinct balls, and we aim to draw all $n$ balls one by one without replacement (meaning once a ball is drawn, it is not returned to the bag) while recording the order in which they are drawn. We need to determine the total number of possible ordered sequences that can be formed.
- First draw: Initially, there are $n$ balls in the bag. For the first draw, we can choose any of the $n$ balls. Thus, there are $n$ possible choices for the first position in the sequence.
- Second draw: After drawing the first ball, $n-1$ balls remain in the bag. For the second draw, we can choose any of these $n-1$ balls. Therefore, there are $n-1$ choices for the second position.
- Third draw: After drawing the second ball, $n-2$ balls are left. For the third draw, we have $n-2$ choices for the third position.
- Continuing the process: This pattern continues for each subsequent draw. For the fourth draw, there are $n-3$ choices, and so on, until we draw the last ball.
- Final draw: When we reach the $n$-th draw, only 1 ball remains in the bag. Thus, there is exactly 1 choice for the last position.
By the multiplication principle, which applies when we make a series of choices in sequence, we multiply the number of options for each draw:$$n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 = n!$$

Example

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

Answer

There are $100!$ ways, which is approximately $9.33 \times 10^{157}$—listing all possibilities would take forever!

Unordered Draws without Replacement

Proposition Unordered Draws without Replacement

The number of different ways to draw $p$ balls from a bag of $n$ balls without replacement and without order is the binomial coefficient $\binom{n}{p}$.

Proof

The number of arrangements can be counted in two ways:

Directly: $\frac{n!}{(n-p)!}$
In two steps:
- The number of combinations of $p$ balls from $n$: $\binom{n}{p}$
- The number of ways to order each combination: $p!$
- By the product rule: $p! \times \binom{n}{p}$

So, by equating the two expressions, $p! \times \binom{n}{p} = \frac{n!}{(n-p)!}$, which implies $\binom{n}{p} = \frac{n!}{p!(n-p)!}$.

A combination is the selection of $p$ items from a set of $n$ items without regard to order.

Example

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

Answer

The number of ways is $\binom{49}{5} = 1,906,884$.

This table summarizes the formulas for counting draws from a bag under different conditions.

	with replacement	without replacement
with order	$n^p$	$\dfrac{n!}{(n-p)!}$ if $p < n$, $n!$ if $p = n$
without order		$\binom{n}{p} = \dfrac{n!}{p!(n-p)!}$

Drawing $p$ balls from a bag of $n$ balls

	with replacement	without replacement
with order	\(n^p\)	\(\dfrac{n!}{(n-p)!}\) if \(p < n\), \(n!\) if \(p = n\)
without order		\(\binom{n}{p} = \dfrac{n!}{p!(n-p)!}\)