Counting Techniques
Your phone passcode has 4 digits. A thief grabs your phone and gets exactly one guess. How likely is it that the thief gets in? To answer, you need to know how many passcodes are possible, and listing them one by one would take forever. This page gives you the tools to count without listing, and then to turn those counts into probabilities.
The Multiplication Principle and Tree Diagrams
Suppose you build an outfit by choosing a hoodie (3 colors) and then sneakers (2 styles). Each hoodie can be paired with each pair of sneakers. Draw it as a tree diagram: every path from left to right is one outfit.
Why does it work? Each option in stage 1 starts its own copy of the stage-2 branches, so you are adding $n_2$ branches $n_1$ times. That is multiplication.
To describe a sample space, write each outcome as an ordered list, such as (panda, green). The principle tells you how many items that list will have before you write it.
A streaming platform allows users to personalize their profile by choosing an avatar from 4 different animals (lion, panda, cat and wolf) and a background color from 3…
A streaming platform allows users to personalize their profile by choosing an avatar from 4 different animals (lion, panda, cat and wolf) and a background color from 3 options (blue, green and orange).
- a) Describe the sample space $E$ of the possible profile combinations.
- b) How many elements does the sample space have? Use the multiplication principle to justify this.
On the menu at your school cafeteria you can choose a starter from salad, pasta or rice; a main course from chicken or fish; and a dessert from fruit or yogurt. a)…
On the menu at your school cafeteria you can choose a starter from salad, pasta or rice; a main course from chicken or fish; and a dessert from fruit or yogurt.
- a) Represent all the possible full menu options using a tree diagram.
- b) If you choose a menu at random, what is the probability that it includes "pasta" as a starter?
Order Matters: Permutations
Suppose you pick several items and the order changes the result (gold, silver, and bronze medals; a passcode). Then you are counting arrangements. There are two cases, depending on whether an item can be used again.
The no-repeat formula comes straight from the multiplication principle: once an item is used, it is gone, so each spot has one fewer option than the one before.
A combination padlock for a locker has a 3-digit code. Each digit can be a number from $1$ to $5$. a) How many different combinations can be created if the numbers can…
A combination padlock for a locker has a 3-digit code. Each digit can be a number from $1$ to $5$.
- a) How many different combinations can be created if the numbers can be repeated?
- b) How many combinations are there if the three numbers must be different?
8 players participate in a local chess tournament. Three different trophies will be awarded for first, second, and third place. a) In how many different ways can the…
8 players participate in a local chess tournament. Three different trophies will be awarded for first, second, and third place.
- a) In how many different ways can the three prizes be awarded?
- b) If last year's champion participates again and we are certain they will finish in the top three, how many podium classifications are possible now?
A streaming content platform uses a security code for parental control. The code consists of 2 letters (from a 26-letter English alphabet) followed by 3 digits (from 0…
A streaming content platform uses a security code for parental control. The code consists of 2 letters (from a 26-letter English alphabet) followed by 3 digits (from 0 to 9).
-
a) How many different codes can be created if letters and numbers can be repeated?
-
b) If a user forgets their code but remembers that it starts with the letter "A" and ends with the number "7", how many possible combinations would they have to try?
-
c) If the code were generated randomly without allowing repetition of any character (letters or numbers), what would be the probability of the code being "BX123"?
Lining Everyone Up: Factorials and Restrictions
If you arrange all $n$ people in a row, the formula gives ${}_nP_n = n!$. For example, 5 people can sit in $5! = 120$ ways.
When a problem adds a condition, use one of these strategies.
Five friends (Ashley, Brandon, Clara, David, and Elena) go to the movies and sit in a row of five consecutive seats. a) In how many different ways can they sit in the…
Five friends (Ashley, Brandon, Clara, David, and Elena) go to the movies and sit in a row of five consecutive seats.
- a) In how many different ways can they sit in the row?
- b) If they decide that Ashley and Brandon must always sit at the two ends of the row, how many different arrangements are possible now?
A fashion designer is creating a capsule collection. For the final fashion show, they have to organize 6 models in a single line. a) In how many different ways can the 6…
A fashion designer is creating a capsule collection. For the final fashion show, they have to organize 6 models in a single line.
-
a) In how many different ways can the 6 models walk the runway?
-
b) If among the models there are two who are sisters and the designer insists that they must walk one immediately after the other, in how many ways can the line be organized now?
-
c) If the designer decides that the two sisters cannot be together under any circumstances, how many options do they have?
Order Doesn't Matter: Combinations
Sometimes you choose a group and the order is irrelevant: a committee, a starting five, a playlist of favorites. Swapping two members gives the same group, so you must not count both orders.
Here is why. The permutation count ${}_nP_r$ counts every group $r!$ times, once for each way to arrange it. Divide by $r!$ to count each group once.
To count a group with a mix of types, count each type separately and multiply.
A music band has prepared 10 songs for their new album, but the record label tells them they can only include 4 of them. a) How many different selections of 4 songs can…
A music band has prepared 10 songs for their new album, but the record label tells them they can only include 4 of them.
- a) How many different selections of 4 songs can they make if the order does not matter?
- b) What are these types of groupings called in combinatorics? Justify your answer.
A group of 12 11th-grade students has been selected to attend a sustainability conference. The school must choose 4 of them to form a committee of spokespersons. a) In…
A group of 12 11th-grade students has been selected to attend a sustainability conference. The school must choose 4 of them to form a committee of spokespersons.
-
a) In how many different ways can the committee be chosen if there is no distinction of roles?
-
b) If among the 12 students there are 7 girls and 5 boys, what is the probability that the committee is formed by exactly 2 boys and 2 girls?
In an inter-school debate tournament, $12$ students participate: $7$ girls and $5$ boys. For the final stage, a team of $4$ representatives must be chosen at random.…
In an inter-school debate tournament, $12$ students participate: $7$ girls and $5$ boys. For the final stage, a team of $4$ representatives must be chosen at random. Calculate the probability that the chosen team simultaneously satisfies the following:
-
There is representation of both sexes.
-
The number of girls is strictly greater than the number of boys.
Counting to Find Probabilities
When all outcomes are equally likely, the theoretical probability of an event is the number of favorable outcomes divided by the number of possible outcomes:
$$P(A) = \frac{\text{number of favorable outcomes}}{\text{number of possible outcomes}}$$Some problems call this Laplace's rule. The counting tools above give you both numbers when the lists are too long to write.
For events, remember the notation. $A \cup B$ ("$A$ or $B$") means at least one happens. $A \cap B$ ("$A$ and $B$") means both happen. $\overline{A}$ ("not $A$," also written $A'$) means $A$ does not happen.
In an 11th-grade class there are 30 students. It is known that 18 of them have passed the last math exam and 12 have passed the English exam. If there are 5 students who…
In an 11th-grade class there are 30 students. It is known that 18 of them have passed the last math exam and 12 have passed the English exam. If there are 5 students who have passed both subjects:
- a) Calculate the probability that, when choosing a student at random, they have passed math or English.
- b) Calculate the probability that they have not passed either of the two subjects.
A ball is drawn from an urn containing 10 balls numbered from $1$ to $10$. We consider the following events: $A = \text{"Getting a prime number"}$…
A ball is drawn from an urn containing 10 balls numbered from $1$ to $10$. We consider the following events:
$A = \text{"Getting a prime number"}$
$B = \text{"Getting a multiple of 3"}$
- a) Write down the elements that make up events $A \cup B$ and $A \cap B$.
- b) Calculate the probabilities $P(A)$, $P(B)$ and $P(A \cup B)$ applying Laplace's rule.
Restrictions on Runs: "No Three in a Row"
Some counting problems forbid a pattern of neighbors. A logistics company prints barcodes with stripes that are black, gray, or white. Without any rule, each stripe has 3 options, so a code with $n$ stripes has $3^n$ possibilities (for 10 stripes, $3^{10} = 59{,}049$).
Now add the rule: no three consecutive stripes of the same color. The multiplication principle alone no longer works, because the number of allowed colors for the next stripe depends on the stripes before it:
-
If the last two stripes are different, the next stripe can be any of the $3$ colors.
-
If the last two stripes are the same, the next stripe must differ from them: only $2$ colors.
So keep track of how each partial code ends. Let $S_n$ be the number of valid codes of length $n$ whose last two stripes are different (or $n = 1$), and $D_n$ the number whose last two stripes are the same. Let $T_n = S_n + D_n$ be the total.
The last formula comes from $T_n = S_n + D_n = 2T_{n-1} + S_{n-1}$ and $S_{n-1} = 2T_{n-2}$.
Continuing the same way gives $T_7 = 1{,}344$, $T_8 = 3{,}672$, $T_9 = 10{,}032$, and $T_{10} = 27{,}408$ valid 10-stripe codes.
Many questions ask about all $3^{10}$ codes, not just the valid ones. For a specific pattern, use the multiplication principle on each spot. For example, if the 5 odd positions are all black (1 option each) and the 5 even positions are white or gray (2 options each), there are $1^5 \cdot 2^5 = 32$ such codes, so $P = \dfrac{32}{59{,}049}$ among all unrestricted codes. Such an alternating pattern never has three alike in a row, so every one of those codes is valid too.
A logistics company organizes its routes using a barcode of $10$ vertical stripes. Each stripe can be black, gray or white. For scanner readability reasons, codes with…
A logistics company organizes its routes using a barcode of $10$ vertical stripes. Each stripe can be black, gray or white. For scanner readability reasons, codes with three consecutive stripes of the same color are not allowed.
-
How many different codes of $10$ stripes can be formed in total (without restrictions)?
-
If a code is chosen at random from all possible ones (without restrictions), what is the probability that the stripes in the odd positions are all black and those in the even positions are all white or gray?
With and Without Replacement
When you draw several items, it matters whether you put each one back.
Try it: draw balls from the urn below, with and without putting them back, and watch how the results change.
Counting also handles "the 2nd success arrives on the 3rd draw."
Counting probabilities can also lead to an equation. Since ${}_nC_2 = \dfrac{n(n-1)}{2}$, you often get a quadratic.
In a toolbox there are 5 Phillips screwdrivers and 3 flathead screwdrivers. 2 screwdrivers are chosen at random, one after the other and without returning the first one…
In a toolbox there are 5 Phillips screwdrivers and 3 flathead screwdrivers. 2 screwdrivers are chosen at random, one after the other and without returning the first one to the box.
-
a) Calculate the probability that both are of the same type.
-
b) Calculate the probability that the second is a flathead given that the first was a Phillips.
-
c) If the experiment were done with replacement, how would the probability in part a) change?
In a toolbox there are $15$ LED bulbs, of which it is known that $3$ are defective. If we extract $4$ bulbs one by one and without replacement: 1. Calculate the…
In a toolbox there are $15$ LED bulbs, of which it is known that $3$ are defective. If we extract $4$ bulbs one by one and without replacement:
-
Calculate the probability that the fourth bulb extracted is the second defective one to appear in the process.
-
If the extractions were done with replacement, would the previous probability change? Justify the answer using counting techniques.
An urn contains $n$ white balls and $6$ red balls. Two balls are extracted simultaneously (or successively without replacement). If it is known that the probability of…
An urn contains $n$ white balls and $6$ red balls. Two balls are extracted simultaneously (or successively without replacement). If it is known that the probability of both balls being white is equal to $1/3$, determine the total number of balls in the urn. (Note: you will need to set up a combinatorial equation and solve it to find the value of $n$).
Conditional Probability and Two-Way Tables
Sometimes you know something extra about the outcome. Then the sample space shrinks to the outcomes where that fact is true.
A two-way table makes this easy. The "given" condition tells you which row or column to look at, and the denominator is that row or column total. Here are 100 students classified by whether they have a part-time job and whether they play a sport.
| Plays a sport | No sport | Total | |
|---|---|---|---|
| Has a job | 18 | 22 | 40 |
| No job | 42 | 18 | 60 |
| Total | 60 | 40 | 100 |
Given a job, 18 of the 40 job-holders play a sport, so $P(\text{sport} \mid \text{job}) = \dfrac{18}{40} = 0.45$. Going the other way, $P(\text{job} \mid \text{sport}) = \dfrac{18}{60} = 0.30$. The two are not the same, because the denominators differ.
Percentages work too. Pick a convenient total (100 or 1,000) and fill in the table. Some problems call this a contingency table.
You can also work with probabilities instead of counts. The part of $A$ outside $B$ has probability $P(A \cap \overline{B}) = P(A) - P(A \cap B)$.
A survey has been carried out among 200 young people about their reading habits and use of social media. The data is collected in the following contingency table: | |…
A survey has been carried out among 200 young people about their reading habits and use of social media. The data is collected in the following contingency table:
| Reads regularly | Does not read regularly | Total | |
|---|---|---|---|
| Uses TikTok > 2h/day | 35 | 85 | 120 |
| Uses TikTok < 2h/day | 55 | 25 | 80 |
| Total | 90 | 110 | 200 |
If we choose a young person at random from this survey, calculate:
-
a) The probability that they read regularly and use TikTok for less than 2 hours a day.
-
b) Given that the young person reads regularly, what is the probability that they use TikTok for more than 2 hours a day?
-
c) Are the events "Reading regularly" and "Using TikTok for more than 2 hours a day" independent? Justify the answer mathematically.
Let $A$ and $B$ be two events in a sample space such that we know their probabilities: $P(A) = 0,6$, $P(B) = 0,4$ and $P(A \cap B) = 0,2$. Calculate the following…
Let $A$ and $B$ be two events in a sample space such that we know their probabilities: $P(A) = 0,6$, $P(B) = 0,4$ and $P(A \cap B) = 0,2$.
Calculate the following probabilities using the properties of probability:
-
a) $P(A \cup B)$
-
b) $P(\bar{A} \cap \bar{B})$ (Probability that neither A nor B occurs).
-
c) $P(A | \bar{B})$ (Probability of A given that B does not occur).
A data analyst studies user behavior on a streaming platform. They have the following information about a sample of $500$ users: $65\%$ are under $25$ years old. $40\%$…
A data analyst studies user behavior on a streaming platform. They have the following information about a sample of $500$ users:
-
$65\%$ are under $25$ years old.
-
$40\%$ of the users use the platform mainly to watch documentaries.
-
Among those who do not watch documentaries, $70\%$ are under $25$ years old.
If a user is selected at random and turns out to be under $25$ years old, calculate the probability that their main preference is documentaries. Use a contingency table to organize the information.
Tree Diagrams and Total Probability
When events happen in stages and the later chances depend on earlier results, a probability tree keeps everything organized. Put the first-stage probabilities on the first branches. On the second branches, put the conditional probabilities, given the branch you are on.
Notice what happened in the last step. Knowing the game was canceled raised the chance of rain from 0.3 to 0.75, because most cancellations come from the "rain" path.
In a local basketball league, the effectiveness of a player's three-point shots has been analyzed. It is known that if they score the first three-pointer, the…
In a local basketball league, the effectiveness of a player's three-point shots has been analyzed. It is known that if they score the first three-pointer, the probability of scoring the second is $0,7$. However, if they miss the first, the probability of scoring the second is only $0,4$. It is known that the probability of scoring the first three-pointer of a game is $0,5$.
-
a) Draw the tree diagram associated with the experiment of shooting two consecutive three-pointers.
-
b) Calculate the probability that the player scores exactly one of the two shots.
-
c) If we know that the player has missed the second shot, what is the probability that they had scored the first?
A technology company manufactures wireless earphones in two plants, one in the US and another in Vietnam. The plant in the US produces $40\%$ of the total and Vietnam…
A technology company manufactures wireless earphones in two plants, one in the US and another in Vietnam. The plant in the US produces $40\%$ of the total and Vietnam the rest. It has been detected that $3\%$ of the earphones from the US have connection faults, while in the Vietnam plant this fault appears in $6\%$ of the production.
-
a) If we buy a pair of earphones at random, what is the probability that they work correctly?
-
b) If we buy a pair of earphones and they turn out to have connection faults, what is the probability that they were manufactured in the plant in the US?
Are Two Events Independent?
Two events are independent if knowing that one happened does not change the chance of the other.
Think of a unit square. If $A$ takes up half the width and $B$ takes up one fifth of the height, the overlap of two independent events is the product of the two fractions.
Independence also explains replacement. Draws with replacement are independent, while draws without replacement are dependent.
It is known that in a certain city it rains on $20\%$ of the days ($LL$), it is very windy on $10\%$ ($V$) and both conditions occur simultaneously on $5\%$. 1.…
It is known that in a certain city it rains on $20\%$ of the days ($LL$), it is very windy on $10\%$ ($V$) and both conditions occur simultaneously on $5\%$.
-
Calculate the probability that on a randomly chosen day it does not rain and it is not windy.
-
Given that it has not rained on a certain day, what is the probability that it was very windy?
-
Are the events "raining" and "being very windy" independent? Prove it mathematically.
Harder Counts: "At Least" and "Exactly"
"At least one" and "at least two" problems have many cases. Count the complement instead.
For exactly $k$ successes in $n$ independent tries, each with success probability $p$, first choose which $k$ tries succeed. Each pattern has the same probability.
$$P(\text{exactly } k) = {}_nC_k \cdot p^k (1-p)^{n-k}$$This is the start of the binomial distribution, which has its own page later.
A computer security system requires passwords to have exactly $8$ characters. These must be chosen from the $26$ letters of the alphabet (case-insensitive) and the $10$…
A computer security system requires passwords to have exactly $8$ characters. These must be chosen from the $26$ letters of the alphabet (case-insensitive) and the $10$ numerical digits ($0-9$). A password is considered "strong" if it contains at least two numerical digits and does not repeat any character. If a program generates a random password that meets the condition of not repeating characters, calculate the probability that it is "strong".
A multiple-choice exam consists of $5$ questions with $4$ answer options each, of which only one is correct. A student who has not studied at all decides to answer at…
A multiple-choice exam consists of $5$ questions with $4$ answer options each, of which only one is correct. A student who has not studied at all decides to answer at random. However, they have a strategy: for each question, they discard one of the options that they know for sure is false (because it is absurd) and choose at random from the remaining three.
-
Calculate the probability that they get exactly $3$ correct answers.
-
What is the probability that they get at least one question right?
Back to the start: a 4-digit passcode with repeats allowed has $10^4 = 10{,}000$ possibilities, so a thief gets in on one guess with probability only $\frac{1}{10{,}000}$.