Counting Techniques
Ximena wants to create a 6-character password for her account, and Diego has to put together a committee of 3 classmates from the 20 in his group. How many different passwords are there? How many committees? Writing them all out is impossible, and without knowing how many there are you can't calculate a probability. That's what counting techniques are for: they tell you how many cases there are without listing them. Afterward you'll use them together with the probability tools that appear in the exercises in this section: events, conditional probability, tree diagrams, Bayes, and the binomial and normal distributions.
The multiplication principle and permutations of n taken r at a time
We start with an intuitive idea: if something is decided in several stages, the options multiply.
Why do we multiply? Because each option from the first stage can be combined with every option from the second, and so on: it's a branching tree.
With replacement (repeats allowed)
If in each of $r$ positions there are the same $n$ options and repeats are allowed, the total is $n^r$.
Without replacement and with order: permutations of $n$ taken $r$ at a time
If you choose $r$ elements out of a total of $n$ without repeating them and order matters ($AB$ is not the same as $BA$), the first position has $n$ options, the second $n-1$ (you already used one), and so on up to $r$ factors.
To improve the security of a mobile app, a developer decides to create access codes consisting of an uppercase letter (from the standard 26-letter alphabet) followed by…
To improve the security of a mobile app, a developer decides to create access codes consisting of an uppercase letter (from the standard 26-letter alphabet) followed by three digits (from 0 to 9).
-
How many different codes can be created if digits can be repeated?
-
How many different codes would there be if the three digits must be distinct from one another?
-
If a code with repeatable digits is generated at random, what is the probability that the letter is a 'Z'?
Ordering all the elements
Permutations of $n$ distinct elements
This is the case $r=n$: you order all the available elements.
With repeated elements
If some letters (or objects) are identical, swapping them doesn't produce a new arrangement. If there are $n$ elements and one appears $a$ times, another $b$ times, etc., you have to divide by the arrangements that can't be told apart:
$$\frac{n!}{a!\,b!\cdots}$$A cybersecurity company generates access keys by permuting the characters of the word BLOCKCHAIN. One of these keys is chosen at random. a) Calculate the probability…
A cybersecurity company generates access keys by permuting the characters of the word BLOCKCHAIN. One of these keys is chosen at random.
- a) Calculate the probability that the chosen key starts and ends with a vowel.
- b) Determine the probability that all the vowels appear together in the key.
- c) Given that the key starts with B, what is the probability that the second letter is an L?
Combinations: choosing when order doesn't matter
If you choose $r$ elements out of $n$ and order doesn't matter (choosing $\{A,B\}$ is the same as $\{B,A\}$), you are counting combinations.
An engineering class has to choose a committee of 3 representatives. If there are 20 students in the class, calculate: In how many ways can the committee be chosen if…
An engineering class has to choose a committee of 3 representatives. If there are 20 students in the class, calculate:
-
In how many ways can the committee be chosen if the three roles (class representative, deputy representative, and secretary) are distinct?
-
In how many ways can it be chosen if the three representatives have equal rank and order does not matter?
-
If there are 12 men and 8 women, what is the probability that the committee (without distinct roles) consists entirely of women? (Express the fraction using combinations).
To improve the security of an esports platform, users are required to create a 6-character password. The first two characters must be uppercase letters of the Spanish…
To improve the security of an esports platform, users are required to create a 6-character password. The first two characters must be uppercase letters of the Spanish alphabet (27 letters) and the remaining four must be digits from $0$ to $9$.
Calculate how many different passwords can be generated if:
- a) Repetitions of letters and numbers are allowed.
- b) Repeating letters is not allowed, but repeating numbers is allowed.
- c) The letters must be distinct and the numbers must form a strictly increasing sequence (for example: $1258$, but neither $1225$ nor $4321$).
Counting to calculate probabilities
When there are too many cases to list, classical probability stays the same; only the way we count changes.
When drawing without replacement (for example, two sensors from a box without putting the first one back), the probabilities are multiplied stage by stage, and by the second draw the contents of the box have already changed: $P(\text{both good}) = \frac{8}{10}\cdot\frac{7}{9}$ in a box with 8 good ones and 2 bad ones. This is better explained with conditional probability, which you'll see later.
An urn contains 12 glass balls for an optics experiment: 5 are blue, 4 are red, and 3 are yellow. If we draw a ball at random, calculate the following probabilities…
An urn contains 12 glass balls for an optics experiment: 5 are blue, 4 are red, and 3 are yellow. If we draw a ball at random, calculate the following probabilities using Laplace's rule:
-
That the ball is red or yellow.
-
That the ball is not blue.
-
That the ball is white.
In a robotics laboratory, 8 proximity sensors in perfect working order and 2 defective sensors have been mixed together in a box. A student draws two sensors…
In a robotics laboratory, 8 proximity sensors in perfect working order and 2 defective sensors have been mixed together in a box. A student draws two sensors consecutively and without replacement (without returning the first one to the box).
Calculate the probability that:
-
Both sensors work correctly.
-
The first is defective and the second is in good working order.
Events, union, and complement
Many problems give counts or probabilities of several events at once and ask you to combine them. A Venn diagram makes it clear.
Why do we subtract $P(A \cap B)$? Because the elements that are in both events were counted twice, once in $A$ and once in $B$.
In an electronic sports (eSports) club, the specialization of its 100 members is analyzed. It is known that 65 of them regularly play League of Legends* (event $L$), 40…
In an electronic sports (eSports) club, the specialization of its 100 members is analyzed. It is known that 65 of them regularly play League of Legends (event $L$), 40 play Valorant (event $V$) and 15 play both video games.
Calculate the probability that, when a member is chosen at random:
- a) They play at least one of the two video games ($L \cup V$).
- b) They play neither of the two.
- c) They play only League of Legends.
Illustrate the situation with a Venn diagram. Here is the starting outline, which you must complete with the number of members in each region:
In a performance study of a new graphics processor, the events $A$: "the processor exceeds $100$ FPS on ultra settings" and $B$: "the processor maintains a temperature…
In a performance study of a new graphics processor, the events $A$: "the processor exceeds $100$ FPS on ultra settings" and $B$: "the processor maintains a temperature below $70^\circ$C" are defined. The following probabilities are known:
$P(A) = 0.65$
$P(B) = 0.50$
$P(A^c \cup B^c) = 0.70$
Find, with reasoning:
- a) The probability that both events occur simultaneously.
- b) The probability that only event $A$ occurs.
- c) Are the events $A$ and $B$ independent? Justify your answer.
Conditional probability and independence
Sometimes you know something extra: "a red card has already come up," "she's a student." That reduces the possible cases and changes the probability.
With a contingency table it's straightforward: the condition tells you which row or column you stay in, and there you divide.
A survey was conducted among the 60 2nd Baccalaureate students at a technological secondary school regarding their use of social media to keep up with science news. The…
A survey was conducted among the 60 2nd Baccalaureate students at a technological secondary school regarding their use of social media to keep up with science news. The results are shown in the following contingency table:
| Use X (Twitter) | Use Instagram | Total | |
|---|---|---|---|
| Male students | 18 | 12 | 30 |
| Female students | 10 | 20 | 30 |
| Total | 28 | 32 | 60 |
If we select a student at random, calculate the probability that:
-
The student is female.
-
They use Instagram to stay informed.
-
Given that the student is male, they prefer to stay informed via the social network X.
A student has two exams on the same day: Mathematics and English. Based on their past marks, they estimate that the probability of passing Mathematics ($M$) is $0.7$,…
A student has two exams on the same day: Mathematics and English. Based on their past marks, they estimate that the probability of passing Mathematics ($M$) is $0.7$, passing English ($I$) is $0.8$, and passing both is $0.6$.
-
Are the events "Passing Mathematics" and "Passing English" independent? Justify your answer mathematically.
-
Calculate the probability that the student passes at least one of the two exams.
Tree diagrams, total probability, and Bayes' theorem
When a process has stages, a tree diagram organizes the calculations: on each branch you write its probability (conditional on the previous branches) and, for a complete path, you multiply the probabilities of its branches.
First, the intuition with a simulation: imagine $1{,}000$ notebooks at a stationery store. $700$ arrive from supplier $A$ and $300$ from $B$. If $3\%$ of those from $A$ and $6\%$ of those from $B$ turn out defective, you'll have $21$ and $18$ defective notebooks. That's $39$ defective in all, and $21$ of them come from $A$. That's exactly what the two formulas below formalize.
In a hospital laboratory, two automatic analyzers, $A$ and $B$, process blood samples. Analyzer $A$ processes $60 \%$ of the samples and $B$ processes the remaining…
In a hospital laboratory, two automatic analyzers, $A$ and $B$, process blood samples. Analyzer $A$ processes $60 \%$ of the samples and $B$ processes the remaining $40 \%$. It is known that $2 \%$ of the samples from analyzer $A$ must be repeated due to a reading error, while for $B$ that percentage is $5 \%$.
Draw the corresponding tree diagram and calculate the probability that a randomly chosen sample must be repeated.
You can do it on paper and send a photo with your answer.
A robotics laboratory has two boxes of components. Box 1 contains $8$ proximity sensors and $4$ actuators. Box 2 contains $5$ proximity sensors and $7$ actuators. A box…
A robotics laboratory has two boxes of components. Box 1 contains $8$ proximity sensors and $4$ actuators. Box 2 contains $5$ proximity sensors and $7$ actuators. A box is chosen at random and two components are drawn successively without replacement.
- a) Calculate the probability that both components drawn are actuators.
- b) Given that both components drawn were proximity sensors, what is the probability that they came from Box 1?
A software development company uses three servers to host its API: server $S_1$ handles $45\%$ of the traffic, $S_2$ handles $35\%$, and $S_3$ handles the rest. Due to…
A software development company uses three servers to host its API: server $S_1$ handles $45\%$ of the traffic, $S_2$ handles $35\%$, and $S_3$ handles the rest. Due to high load, server $S_1$ fails (error 500) in $2\%$ of requests, $S_2$ in $3\%$, and $S_3$ in $5\%$.
- a) If a user makes a request, what is the probability that the server returns an error?
- b) If a request has failed, what is the probability that it was handled by server $S_3$?
The harder exercises of this type mix stages (the contents of an urn change after a ball is moved from another) or ask you to decide on dependence from data; they are solved the same way: tree diagram, total probability, Bayes, and comparing $P(A\cap B)$ with $P(A)P(B)$.
A data storage server receives requests from three types of clients: Bronze ($50\%$), Silver ($30\%$) and Gold ($20\%$). Due to saturation, the server may reject…
A data storage server receives requests from three types of clients: Bronze ($50\%$), Silver ($30\%$) and Gold ($20\%$). Due to saturation, the server may reject requests. It is known that the probability of a request being rejected is $10\%$ for Bronze clients, $5\%$ for Silver clients and $1\%$ for Gold clients.
- a) If a request is selected at random and turns out to be rejected, what is the probability that it comes from a Bronze client?
- b) Following a system update, the overall probability of rejection has dropped to $4\%$. If the probabilities for Silver and Gold clients remain the same, what is the new probability of rejection for Bronze clients?
An urn $A$ contains 4 white balls and 6 black balls, and an urn $B$ contains 7 white balls and 3 black balls. A fair die is rolled: if a number less than or equal to 2…
An urn $A$ contains 4 white balls and 6 black balls, and an urn $B$ contains 7 white balls and 3 black balls. A fair die is rolled: if a number less than or equal to 2 is obtained, a ball is drawn from urn $A$ and placed into urn $B$, and then a ball is drawn from $B$. If a number greater than 2 is obtained, a ball is drawn from urn $B$ and placed into urn $A$, and then a ball is drawn from $A$.
Calculate the probability that the second ball drawn is white.
An electronic device consists of two critical components, $C_1$ and $C_2$, connected in parallel (the device functions if at least one of the two functions). The…
An electronic device consists of two critical components, $C_1$ and $C_2$, connected in parallel (the device functions if at least one of the two functions). The probability that $C_1$ fails within a year is $0.15$, and that $C_2$ fails is $0.20$. However, the failures are not independent: if $C_1$ fails, the probability that $C_2$ also fails increases to $0.60$.
- a) Calculate the probability that the device fails within a year.
- b) Are the events "$C_1$ fails" and "$C_2$ fails" dependent? Justify your answer with calculations.
- c) If the device has failed, what is the probability that component $C_1$ has failed?
The binomial distribution
Imagine repeating an experiment $n$ times, independently, with only two outcomes ("success" with probability $p$ and "failure" with $q=1-p$). The number of successes $X$ follows a binomial distribution $B(n,p)$.
For "at least one" or "at least two," the complement is convenient: $P(X \ge 1) = 1 - P(X=0)$, and $P(X\ge 2)=1-P(X=0)-P(X=1)$.
A telecommunications engineer estimates that the probability of a data packet being lost during a wireless transmission under interference conditions is $0.15$. A burst…
A telecommunications engineer estimates that the probability of a data packet being lost during a wireless transmission under interference conditions is $0.15$. A burst of $10$ packets is sent independently.
- a) What is the probability that exactly $3$ packets are lost?
- b) Calculate the probability that at least $2$ packets are lost.
- c) What is the expected number of lost packets and their standard deviation?
The normal distribution
Many variables (heights, commute times, grades) cluster around an average in a bell shape. It is written $X \sim N(\mu, \sigma)$, where $\mu$ is the mean and $\sigma$ the standard deviation.
To calculate probabilities you standardize: $Z = \dfrac{X-\mu}{\sigma}$ counts how many standard deviations $X$ is from the mean and follows an $N(0,1)$. You use the cumulative table $P(Z \le z)$ or a calculator or GeoGebra.
The measures that describe data are: mean (average), median (middle value), mode (the most frequent), range (maximum minus minimum), variance (the average of the squared deviations), and standard deviation (its square root).
The compilation time of a complex engineering project follows a normal distribution with a mean of $120$ seconds and a standard deviation of $15$ seconds. a) Calculate…
The compilation time of a complex engineering project follows a normal distribution with a mean of $120$ seconds and a standard deviation of $15$ seconds.
- a) Calculate the probability that the project compiles in under $100$ seconds.
- b) Calculate the probability that the compilation time is between $110$ and $140$ seconds.
- c) What compilation time is exceeded by only $5\%$ of the slowest processes?
In a technical certification exam, scores follow a $N(70, 12)$ distribution. The institution decides to award an "Excellence Commendation" to students who achieve a mark…
In a technical certification exam, scores follow a $N(70, 12)$ distribution. The institution decides to award an "Excellence Commendation" to students who achieve a mark in the $90$ percentile.
- a) What is the minimum mark required to receive this commendation?
- b) If $250$ students take the exam, how many are expected to receive the commendation?
- c) If we choose two students at random, what is the probability that both receive the commendation?
The response time of an industrial sensor follows a normal distribution $N(\mu, \sigma)$. It is known that $15.87\%$ of response times take more than $82$ milliseconds,…
The response time of an industrial sensor follows a normal distribution $N(\mu, \sigma)$. It is known that $15.87\%$ of response times take more than $82$ milliseconds, and that only $2.28\%$ of response times are faster than $58$ milliseconds.
- a) Calculate the parameters $\mu$ and $\sigma$ of the response time.
- b) If the manufacturer guarantees that the sensor responds in less than $85$ ms, what percentage of sensors will not satisfy the guarantee?
In an engineering exam taken by 100 students, the marks follow a normal distribution with mean $6.2$ and standard deviation $1.5$. The lecturer decides that the top…
In an engineering exam taken by 100 students, the marks follow a normal distribution with mean $6.2$ and standard deviation $1.5$. The lecturer decides that the top $10\%$ of students with the highest marks will receive an "Outstanding" grade, whilst those whose mark is more than one standard deviation below the mean will fail.
- a) What is the minimum mark required to obtain an "Outstanding"?
- b) How many students are expected to fail the exam?
- c) If we choose three students at random, what is the probability that at least one of them has a mark above 7?
Approximating the binomial with the normal
If $n$ is large, calculating $\binom nk$ for many values of $k$ is tedious, and the shape of $B(n,p)$ resembles a bell curve. So you use $N(np, \sqrt{npq})$.
A social network detects that $10\%$ of created accounts are "bots". If $400$ new accounts are registered in one hour: a) Explain why the number of bots can be…
A social network detects that $10\%$ of created accounts are "bots". If $400$ new accounts are registered in one hour:
- a) Explain why the number of bots can be approximated using a normal distribution.
- b) Using the normal approximation with continuity correction, calculate the probability that there are between $35$ and $50$ bots (inclusive).
- c) Calculate the probability that the number of bots is greater than $45$.
A satellite communication system transmits data packets. Each packet has an independent probability $p = 0.002$ of becoming corrupted during transmission. To ensure…
A satellite communication system transmits data packets. Each packet has an independent probability $p = 0.002$ of becoming corrupted during transmission. To ensure reception, a block of $2500$ packets is sent.
- a) Justify why the number of corrupted packets can be approximated by a normal distribution.
- b) Calculate the probability that between 4 and 8 packets (inclusive) are corrupted.
- c) If the error correction system can only repair up to 10 packets per block, what is the probability that the block is unrepairable?
Continuous variables: density function
If a variable can take any value in an interval (a measurement error, a time), its probability is measured with areas under a density function $f(x)$.
A laser aiming system for eye surgery has a deviation error $X$, measured in micrometres, which follows a probability density function given by: $$f(x) = \begin{cases}…
A laser aiming system for eye surgery has a deviation error $X$, measured in micrometres, which follows a probability density function given by:
$$f(x) = \begin{cases} k(4x - x^3) & \text{if } 0 \le x \le 2 \\ 0 & \text{otherwise} \end{cases}$$- a) Determine the value of the constant $k$ so that $f(x)$ is a valid probability density function.
- b) Calculate the probability that the deviation is greater than 1 micrometre.
- c) Obtain the expected value of the deviation. What does this value mean in the context of the surgery?
Back to the start: if Ximena's $6$-character password uses lowercase letters and digits ($26+10=36$ options per spot), there are $36^6 = 2{,}176{,}782{,}336$ possible passwords. And for Diego's committee, $3$ out of $20$, order doesn't matter: there are $C(20,3)=1{,}140$ different committees.