Introduction to Counting
Your phone asks for a 6-digit passcode. How many different passcodes are possible? And how many of them have no repeated digit? Listing them one by one would take forever. Combinatorics is the art of counting without listing. In AP Statistics you will need it to find probabilities, and later for the binomial distribution. This page gives you the basic tools.
The multiplication principle
A shop sells ice cream orders with 4 sizes, 6 flavors and 3 toppings. To place an order you make one choice at each stage, and each choice does not affect the others.
Rolling two dice is the same idea: 6 outcomes on the first die and 6 on the second give $6 \cdot 6 = 36$ outcomes. Try it:
A restaurant offers a set menu with $4$ appetizers, $3$ main courses and $5$ desserts. In how many different ways can you order a full menu consisting of an appetizer, a…
A restaurant offers a set menu with $4$ appetizers, $3$ main courses and $5$ desserts. In how many different ways can you order a full menu consisting of an appetizer, a main course and a dessert?
A bicycle brand manufactures a model that is available in $3$ different frame sizes, $5$ colors and with $2$ different types of brakes. How many different versions of…
A bicycle brand manufactures a model that is available in $3$ different frame sizes, $5$ colors and with $2$ different types of brakes. How many different versions of this bicycle model exist on the market?
To go from city A to city B there are $3$ different roads, and to go from city B to city C there are $2$ different roads. In how many ways can you travel from A to C,…
To go from city A to city B there are $3$ different roads, and to go from city B to city C there are $2$ different roads.
-
In how many ways can you travel from A to C, necessarily passing through B?
-
Draw the corresponding tree diagram for this journey.
The addition principle
Now suppose you do not do both things, but choose between two alternatives. To get from Chicago to Milwaukee you can take one of 4 trains or one of 3 buses.
In a classroom library there are $12$ science fiction novels, $8$ historical novels and $5$ biographies. If you only have time to read one book this weekend, how many…
In a classroom library there are $12$ science fiction novels, $8$ historical novels and $5$ biographies. If you only have time to read one book this weekend, how many different options do you have to choose from?
A password for a computer system must be formed by $2$ letters of the alphabet (out of $26$ possible letters) followed by $3$ digits (from $0$ to $9$), or by $3$ letters…
A password for a computer system must be formed by $2$ letters of the alphabet (out of $26$ possible letters) followed by $3$ digits (from $0$ to $9$), or by $3$ letters followed by $2$ digits. If both letters and digits can be repeated, how many different passwords can be created in total?
Tree diagrams
A tree diagram lists every outcome of a multi-stage process. Each stage is a level of branches, and each path from the root to the end is one outcome. Counting the ends of the branches gives the same number as the multiplication principle.
Here is a case where the options change from stage to stage. Ava, Ben and Cam are candidates, and the class picks a president and then a vice president, who must be a different person.
There are 3 choices for president, and after that only 2 choices for vice president, so $3 \cdot 2 = 6$ leaves. The number of options in the second stage changed (3, then 2), but it was the same in every branch. That is why multiplying still works.
Draw the tree diagram for the experiment consisting of tossing a fair coin and then rolling a tetrahedral die (with its faces numbered from $1$ to $4$). How many…
Draw the tree diagram for the experiment consisting of tossing a fair coin and then rolling a tetrahedral die (with its faces numbered from $1$ to $4$). How many possible outcomes does this compound experiment have?
In an urn there are $3$ red balls and $2$ blue balls. Two balls are drawn consecutively and without returning them to the urn (without replacement). Draw the tree…
In an urn there are $3$ red balls and $2$ blue balls. Two balls are drawn consecutively and without returning them to the urn (without replacement). Draw the tree diagram of the experiment and calculate how many different outcomes can be obtained if we take into account the order of extraction and the color of the balls.
Trees that stop early
Some processes end as soon as a condition is met, such as a playoff series. Then the branches do not all have the same length, and $2 \cdot 2 \cdot 2$ would count games that are never played. Drawing the tree is the safest method.
Two basketball teams, Alpha and Beta, play a best-of-$3$ playoff series (the first to win $2$ matches qualifies). Draws are not possible. Draw the tree diagram with all…
Two basketball teams, Alpha and Beta, play a best-of-$3$ playoff series (the first to win $2$ matches qualifies). Draws are not possible. Draw the tree diagram with all possible outcomes of the playoff. In how many different ways can the series of matches unfold?
Two friends, Daniel and Diana, play a board game consisting of several rounds. The final winner of the game will be the first to win $2$ consecutive rounds or $3$ rounds…
Two friends, Daniel and Diana, play a board game consisting of several rounds. The final winner of the game will be the first to win $2$ consecutive rounds or $3$ rounds in total throughout the game. Knowing that draws are not possible in any round, draw the corresponding tree diagram and determine the maximum number of rounds they can play and how many different outcomes the game has.
Counting paths on a grid
A robot moves along grid lines, only right or up, from A to B. A path is a sequence of moves, and counting it with a tree would be long. Use the addition principle instead.
The robot reaches any point from the point just to its left or from the point just below it, and those are the only possibilities. These two groups do not overlap, so:
$$\text{paths to a point} = \text{paths to the point on the left} + \text{paths to the point below}$$Points on the bottom row and on the left column have just 1 path. Fill in the rest point by point.
Look at the grid in the figure. A robot moves from point A to point B moving only to the right or upwards along the grid lines. How many different paths can the robot…
Look at the grid in the figure. A robot moves from point A to point B moving only to the right or upwards along the grid lines. How many different paths can the robot take to reach its destination?
Repetition and no repetition
Most counting problems come down to one question: can things be reused? Each stage gets its own count of options.
Answer sheets are a classic case of repetition. Each question is one stage, and the same letter can be used on many questions. Leaving a question blank is one more "answer" you can choose, so it adds one option to every stage.
A multiple-choice exam consists of $10$ questions. Each question has $4$ answer options, of which only one is correct. In how many different ways can the exam be…
A multiple-choice exam consists of $10$ questions. Each question has $4$ answer options, of which only one is correct.
-
In how many different ways can the exam be answered if it is compulsory to mark an option for all questions?
-
In how many ways could it be answered if leaving questions blank is allowed?
We want to design a flag with $3$ vertical stripes using a palette of $5$ available colors. In how many ways can it be colored if two adjacent stripes cannot have the…
We want to design a flag with $3$ vertical stripes using a palette of $5$ available colors.
-
In how many ways can it be colored if two adjacent stripes cannot have the same color?
-
In how many ways can it be colored if, in addition to the previous condition, the first and last stripes must also necessarily be of different colors?
In a class of $20$ students, a management team consisting of a president, a vice president, and a secretary must be chosen (different roles that cannot be held by the…
In a class of $20$ students, a management team consisting of a president, a vice president, and a secretary must be chosen (different roles that cannot be held by the same person simultaneously). Once the management team is chosen, a sports representative must be selected from the remaining $17$ students. In how many different ways can this entire selection process be carried out?
Restrictions and the complement trick
Sometimes a condition limits one position, such as "even number", "first digit not zero" or "palindrome". Two strategies help.
Using only the digits from the set $\{1, 2, 3, 4, 5\}$: How many numbers of $4$ different digits can be formed? How many of those formed numbers are even?
Using only the digits from the set $\{1, 2, 3, 4, 5\}$:
-
How many numbers of $4$ different digits can be formed?
-
How many of those formed numbers are even?
A palindromic number is one that reads the same from left to right as from right to left (for example, the number $35153$). How many palindromic numbers of $5$ digits…
A palindromic number is one that reads the same from left to right as from right to left (for example, the number $35153$).
-
How many palindromic numbers of $5$ digits exist in total?
-
How many of those palindromic numbers of $5$ digits are even numbers?
In the decimal number system, we consider all integers between $1000$ and $9999$ (both inclusive). How many of these numbers contain the digit $7$ at least once in their…
In the decimal number system, we consider all integers between $1000$ and $9999$ (both inclusive). How many of these numbers contain the digit $7$ at least once in their writing?
Factorials
When you arrange items and one fewer is available at each step, the same product keeps appearing: $n \cdot (n-1) \cdot (n-2) \cdots 1$. It has its own name and symbol.
Why $0! = 1$? Because $n! = n \cdot (n-1)!$. Put $n = 1$: $1! = 1 \cdot 0!$, and since $1! = 1$, we need $0! = 1$.
A calculator has an $n!$ key, usually in the probability menu. To simplify a fraction of factorials, do not expand everything. Write the bigger factorial down to the smaller one and cancel.
A product of descending numbers can be written with factorials by "completing" the rest of the factorial and dividing it out:
Calculate the value of the following numerical expressions using the properties of factorials: $\frac{8!}{6!}$ $4! + 3!$
Calculate the value of the following numerical expressions using the properties of factorials:
-
$\frac{8!}{6!}$
-
$4! + 3!$
Express the following products using mathematical factorial notation: $15 \cdot 14 \cdot 13$ $7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$
Express the following products using mathematical factorial notation:
-
$15 \cdot 14 \cdot 13$
-
$7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1$
Factorials with variables
The same idea of expanding the bigger factorial works with algebra. Always use $(k+1)! = (k+1) \cdot k!$, going down only as far as you need.
$$\frac{(x+3)!}{x!} = \frac{(x+3)(x+2)(x+1)\,x!}{x!} = (x+3)(x+2)(x+1)$$Simplify the algebraic expression $\frac{(x+2)!}{x!}$ and then solve the equation $\frac{(x+2)!}{x!} = 72$.
Simplify the algebraic expression $\frac{(x+2)!}{x!}$ and then solve the equation $\frac{(x+2)!}{x!} = 72$.
Solve the following equation with factorials, knowing that $n$ is a natural number: $$ \frac{(n+1)!}{(n-1)!} - \frac{(n-1)!}{(n-3)!} = 22 $$
Solve the following equation with factorials, knowing that $n$ is a natural number:
$$ \frac{(n+1)!}{(n-1)!} - \frac{(n-1)!}{(n-3)!} = 22 $$Prove algebraically the following identity valid for any natural number $n \ge 1$: $$ n! + (n-1)! = (n+1) \cdot (n-1)! $$ Once proven, apply this result to simplify and…
Prove algebraically the following identity valid for any natural number $n \ge 1$:
$$ n! + (n-1)! = (n+1) \cdot (n-1)! $$Once proven, apply this result to simplify and calculate the exact value of the expression $\frac{10! + 9!}{11!}$.
The pigeonhole principle
If there are more pigeons than pigeonholes, some pigeonhole must hold at least two pigeons. It sounds obvious, but it is a powerful tool: it can guarantee that something repeats without finding which one.
Geometry can supply the boxes too. In a $3 \times 3$ square, pick any 10 points. Cut the square into nine $1 \times 1$ squares. Since $10 > 9$, some small square holds two points. The farthest apart two points can be in a unit square is its diagonal, $\sqrt{2}$, so those two points are at most $\sqrt{2}$ apart. The strategy is to cut the figure into "strategic regions" whose size you control. (With 5 points in a square of side 2, the same idea uses four $1 \times 1$ squares as the boxes.)
In a chest of drawers there are loose socks of $3$ different colors (black, white and blue). If there is a power outage and you take out socks in the dark, what is the…
In a chest of drawers there are loose socks of $3$ different colors (black, white and blue). If there is a power outage and you take out socks in the dark, what is the minimum number of socks you must draw to ensure you have at least one pair of the same color?
In a high school there are $400$ enrolled students. Justify mathematically why you can be sure that at least two students have their birthday on the same day of the…
In a high school there are $400$ enrolled students.
-
Justify mathematically why you can be sure that at least two students have their birthday on the same day of the year.
-
What is the minimum number of students needed in the school to guarantee that at least three of them share a birthday? (Consider non-leap years of $365$ days).
$5$ points are chosen at random inside a square of side $2\text{ cm}$. Prove, using the pigeonhole principle, that there will always be at least two points whose…
$5$ points are chosen at random inside a square of side $2\text{ cm}$. Prove, using the pigeonhole principle, that there will always be at least two points whose distance between them is less than or equal to $\sqrt{2}\text{ cm}$. (Hint: divide the square into strategic regions).
Back to the start: a 6-digit passcode has 6 positions with 10 digit choices each, so there are $10^6 = 1{,}000{,}000$ passcodes. With no repeated digit the options shrink at each stage: $10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 = 151{,}200$.