Counting Outcomes Combinations and Permutations
Brief overview of counting methods used to determine the number of possible outcomes under different scenarios. These are then used to compute probabilities of events.
What are Outcomes?
An outcome is a possible state of a system or experiment. For example, if we flip a coin twice, the possible outcomes are the following, $HH$, $HT$, $TH$, and $TT$.
In statistics, the set of all possible outcomes is called the sample space, denoted by $\Omega$. So, in the above example, $\Omega={HH, HT, TH, TT}$. Each member of the sample space set, for example, $HT$, is a possible outcome, also known as sample outcome or realization, denoted by $\omega$.
Events are subsets of the sample space $\Omega$, i.e., sets of sample outcomes. For example, in an experiment where a coin is flipped twice, the event $E$ that the first coin flip is $T$ is the subset of $\Omega$, $E={TH, TT}$.
Computing Likelihood of Events
Assuming that all possible outcomes are equally likely, the probability of an event $E$ can be calculated as follows:
\[P(E)=\frac{\vert E \vert}{\vert \Omega \vert}\]where $\vert E \vert$ is the cardinality of set $E$, i.e. a count of the sample outcomes that satisfy event $E$, and $\vert \Omega \vert$ is the cardinality of the sample space $\Omega$, i.e. count of all sample outcomes present in the sample space set.
In the above example, where a coin is flipped twice, we can easily get the counts (cardinality) of the sets $E$ and $\Omega$, because we can list all the possible outcomes manually and count how many are in each set.
So, since $\Omega={HH, HT, TH, TT}$ and $E={TH, TT}$, we know that $\vert \Omega \vert=4$ and $\vert E \vert = 2$.
Hence:
\[P(E)=\frac{\vert E \vert}{\vert \Omega \vert}=\frac{2}{4}=0.5\]Enumeration and Counting Does Not Scale
While listing all possible outcomes making up the sample space of an experiment is feasible for very small experiments, it quickly becomes impracticable, even with modest increases in complexity. For example, if instead of flipping a coin twice we had to flip it 10 times, we would need to list 1024 sample outcomes to complete the sample space, instead of just 4.
Clearly, we need a better way to compute the number of possible outcomes and the number of outcomes satisfying an event $E$. First, however, we need to learn about order (permutations and combinations) and picking options (with or without replacement), to be able to identify the type of problem at hand so as to use the correct function to compute the count of relevant outcomes.
Permutations, Combinations and Replacements
In mathematics, permutations are lists in which order matters. So, for example, $ABC$ is considered different from $ACB$ or $BAC$. Combinations on the other hand do not care about order, so $ABC$, $ACB$ and $BAC$ are considered one and the same.
To generate permutations or combinations a set of values is used from which members are drawn to form a new list. If a set member can only be used once in the creation of a list, we say we are picking values without replacement. Alternatively, if a set member can be used multiple times we are picking values with replacement.
Examples
Let us consider four simple examples to explain each possibility, i.e. permutations with replacement, permutations without replacement, combinations without replacement and finally combinations with replacment.
In the four examples below, imagine that we have three colours, red, yellow and blue, as follows.
Permutation with replacement
Now, say we are interested in picking two colours to place side by side for a fictional flag. Order clearly matters in this case, so this is a permutation. Furthermore, the same colour can be picked more than once, so it is being replaced. The total number of outcomes in such a scenario is $9$, as follows.
Permutation without replacement
Next, imagine that for our fictional flag we do not want the same colour to be used twice. In this case, we are picking colours without replacement. However, this is still a permutation since order still counts. Here, $6$ outcomes are possible in total, since we remove the bottom row of flags from the options illustrated above, as follows.
Combinations without replacement
We now decide that each flag should have a unique pair of colours so that we do not get confused between them. The order of colours on our fictional flags does not count anymore and thus this is no longer a permutation but a combination. Furthermore, colours cannot be used twice so we are picking colours without replacement. In this scenario, there are only $3$ possible flags, as follows
Combinations with replacement
We finally decide that, yes, each flag should have its own colours but the same colour can be picked twice to make one solid colour flag. In this final scenario, we are still dealing with a permutation but now we are picking colours with replacement, making it possible to design $6$ unique fictional flags, as follows.
Compute Number of Outcomes for a Permutation With Replacement
In the flag example, we had $3$ colours from which to choose and we wanted to pick $2$ at a time. The order colours were picked in counted, so it is a permutation, and the colours could be picked more than once, so we were picking with replacement.
Therefore, for our first colour pick we had $3$ options from which to choose. For our second colour, we also had $3$ colours, since colours were being replaced. So in all we have $3 \times 3=9$ possible flags.
More formally, if $n$ is the number of options and $k$ the number of items we need to pick, if we are picking with replacement, then the number of possible outcomes is:
\[\textit{possible outcomes}=n^k\tag{1}\label{1}\]So, in our example $n^k = 3^2 = 9$ possible flags.
We can now compute more complex examples, say what are the possible flags if we pick $2$ colours with replacement from $20$ different colours.
\[n=20, k=2\] \[n^k = 20^2 = 400 flags\]What about flags with $3$ colours?
\[n=20, k=3\] \[n^k = 20^3 = 8000 flags\]Compute Number of Outcomes for a Permutation Without Replacement
For our first pick, we have all options available, $n$. For our second choice, since we are not replacing options, we now have $n-1$ options. If we had to pick a third choice, we would now have to pick from $n-2$ options.
More generally, with $n$ options and $k$ picks without replacement, the number of possible outcomes is:
\[\prod_{i=n-k+1}^n i\]This can be computed more easily using factorials, as follows:
\[\frac{n!}{\left(n-k\right)!}\tag{2}\label{2}\]Compute Number of Outcomes for a Combination Without Replacement
This is similar to the permutation without replacement, only order does not count here, so we need to remove entries which are just permutations of themselves.
To do so, we first need to compute how many permutations without replacement there are for each item. We already know how to do this. Since each item consists of $k$ picks, we know $n=k$ and so the permutations without replacement possible with $k$ picks is equal to $\frac{n!}{\left(n-k\right)!} = \frac{k!}{\left(k-k\right)!} = k!$ permutations.
Therefore, the total number of combinations without replactment is:
\[\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}\tag{3}\label{3}\]$\binom{n}{k}$ is read, n choose k, and is also known as the binomial coefficient.
Taking our previous example, where we had $n=3$ colours and we had to pick $k=2$ colours without replacement, the number of possible flags is:
\[\binom{3}{2}=\frac{3!}{2!\left(3-2\right)!}=3\]Compute Number of Outcomes for a Combination With Replacement
To compute the number of outcomes for a combination with replacement, we will use the function to compute combinations without replacement, but replace $n$ with $n-1+k$, so instead of $\binom{n}{k}$ we use $\binom{n-1+k}{k}$, which is equal to:
\[\binom{n-1+k}{k}=\frac{\left(n-1+k\right)!}{k!\left(n-1+k-k\right)!}\] \[\binom{n-1+k}{k}=\frac{\left(n-1+k\right)!}{k!\left(n-1\right)!}\tag{4}\label{4}\]Explanation of Combination With Replacement Formula
To understand why this is the case we need to look at the problem from a new perspective. Instead of finding all the combinations with replacement of length $k$ from $n$ options, we will find valid permutations of actions of length $n-1+k$ that include exactly $k$ pick actions that produce the desired outcome, i.e., combinations with replacement of length $k$ from $n$ options.
To explain this better, let us use the flag example once more. Imagine that to pick colours for the flag we are using a robotic arm that always starts on top of the first option from the left, red in this case. Below the robotic arm is illustrated as a white vertical line.
| | |
The robotic arm can only move to the right, one option at a time, and in the end it must always be positioned on the rightmost option. Thus, in this example, when the flag colour selection process is complete, the robotic arm will be positioned on blue as illustrated below.
| | |
If we use $M$ to represent a move of the robotic arm to the right and $P$ to represent picking the colour currently underneath the robotic arm, then to pick $2$ colours with replacement, i.e. repetitions are allowed, out of $3$ colour options we will need to have permutations made up of $2$ $M$’s and $2$ $P$’s.
For instance, the sequence $MPMP$ would look like this, where a white circle represents the robotic arm picking a colour.
| | | | | o | | | o | |||||||||||||||||
| $M$ | $P$ | $M$ | $P$ | = | |||||||||||||||||
Note: For $n$ options we will always require $n-1$ $M$’s (move actions) and $k$ $P$’s (pick actions), so action permutations must be of length $n-1+k$.
We therefore need to generate permutations with replacement, repetitions allowed, from $2$ actions, $M$ and $P$, of length $n-1+k$. We can compute how many of those are possible by adapting the $n^k$ formula for our needs, becoming $2^{n-1+k}$. For the flag example, with $n=3$ colour options and flags having $k=2$ colours, this is equal to $2^{3-1+2}=2^4=16$ possible action permutations with replacement.
This, however, is not the correct answer, since $\frac{\left(n-1+k\right)!}{k!\left(n-1\right)!} = \frac{\left(3-1+2\right)!}{2!\left(3-1\right)!} = \frac{4!}{2!2!} = 6$ possible combinations with replacement of length $2$ from $3$ options.
The reason for this is that not all the action permutations generated are valid. For instance, the following permutations of length $4$ are invalid for our needs in the flag example, because they either pick less or more than the $k$ colours required.
$MMMM$, $PMMM$, $PPMP$, $MPPP$, $PPPP$.
Solution
We know that for the action permutations to be valid they must be of length $n-1+k$ and each one must contain exactly $k$ $P$ actions. So there are $n-1+k$ positions where the $k$ $P$ actions can be placed. The other positions are implicitly $M$ actions. Figuring out the number of combinations without replacement of length $k$ possible from $n-1+k$ positions can be computed using the binomial coefficient.
\[\binom{n}{k}=\frac{n!}{k!\left(n-k\right)!}\]Replacing $n$ with $n-1+k$ for our needs we get:
\[\binom{n-1+k}{k}=\frac{\left(n-1+k\right)!}{k!\left(n-1\right)!}\]The table below shows the possible combinations without replacement for the pick action position in the action sequence permutations for the flag example, with $n=3$ colour options and $k=2$ coloured flags.
| Position | 1 | 2 | 3 | 4 |
|---|---|---|---|---|
| P | P | |||
| P | P | |||
| P | P | |||
| P | P | |||
| P | P | |||
| P | P |
Combinations and Permutations in Action
Let us look at some scenarios where computing combinations and permutations comes in handy.
Computing Probability of Getting Exactly $k$ (Successful) Outcomes Out of $n$ Trials
Suppose we have a fair coin and we are going to flip it $5$ times. What is the probability of getting exactly $3$ heads?
Let us start by defining event $E$ as getting exactly $3$ heads in $5$ fair coin flips.
Since this is a fair coin, $P(H)=P(T)=\frac{1}{2}$.
Each coin flip $f$ is independent, and so $P(outcome) = P(f_1)P(f_2)P(f_3)P(f_4)P(f_5)$
The probability of a desired outcome, i.e., one having exactly $3$ heads, is $P(3H2T)=P(H)^3P(T)^2=\left(\frac{1}{2}\right)^3\left(\frac{1}{2}\right)^2=\frac{1}{32}$
Next, we need to compute how many ways can $3$ heads be organized if we have $5$ positions (trials) available. This is a problem that can be solved using the binomial coefficient used to compute the number of combinations without replacement (repetition) possible. These are combinations since getting a head on the first, second and third trial is exactly the same like geting a head on the third, second and first trial, so order does not matter.
Since we have $5$ flips and want $3$ heads, this is an $\binom{5}{3}$ problem, that works out to $\frac{5!}{3!\left(5-3\right)!}=\frac{5!}{3!2!}=\frac{5\cdot4}{2}=10$ possible combinations.
We can now compute the probability of event $E$.
\[P(E) = \frac{1}{32} \times 10 = \frac{10}{32} = \frac{5}{16}\]General Form
Let $m$ be the number of possible outcomes of a trial, for example, $2$ for a coin and $6$ for a dice, $n$ be the number of trials and $k$ the number of successes we want.
Then, let $p$ be the probability of success and $q=1-p$ the probability of failure. If all trial outcomes are equally likely, then $p = \left(\frac{1}{m}\right)$ and $q = \frac{m-1}{m}$.
The probability of getting exactly $k$ successes in $n$ trials, event $E$, is then:
\[P(E)=\binom{n}{k}p^kq^{n-k}\tag{5}\label{5}\]If all trial outcomes are equally likely, this is equal to:
\[P(E)=\binom{n}{k}{\frac{1}{m}}^k{\frac{m-1}{m}}^{n-k}\]Let us apply the above formula to the previous problem.
\[P(E)=\binom{n}{k}{\frac{1}{m}}^k{\frac{m-1}{m}}^{n-k}\] \[P(E)=\binom{5}{3}{\frac{1}{2}}^3{\frac{2-1}{2}}^{5-3}\] \[P(E)=\binom{5}{3}{\frac{1}{2}}^3{\frac{1}{2}}^{2}=10{\frac{1}{2}}^3{\frac{1}{2}}^{2}=\frac{10}{32}=\frac{5}{16}\]Refer to Bernoulli Trial and Binomial Distribution for more details.
Computing Probability of Getting At Least $k$ (Successful) Outcomes Out of $n$ Trials
Suppose we have a fair coin and we are going to flip it $5$ times. What is the probability of getting at least $4$ heads?
One way of solving this is to compute the probability of getting exactly $4$ heads and add it to the probability of getting exactly $5$ heads. There are $\binom{5}{4}=5$ combinations to get exactly $4$ heads in $5$ trials, namely $HHHHT$, $HHHTH$, $HHTHH$, $HTHHH$, $THHHH$. There is clearly $1$ way to get exactly $5$ heads in $5$ trials, $HHHHH$.
Using the formula for permutations with repetition, we know that there are $2^5=32$ possible permutations of flipping a coin $5$ times. Hence, the probability of getting at least $4$ heads in $5$ coin flips is $\frac{5+1}{32}=\frac{6}{32}=\frac{3}{16}$.
We can adapt equation $\eqref{5}$ to build a general formula to solve problems where we need to compute the probability of getting at least $k$ successes in $n$ trials, as follows:
\[P(E)=\sum_{j=k}^{n}\binom{n}{j}p^jq^{n-j}\tag{6}\label{6}\]Solving the current question using equation \eqref{6} gives:
\[P(E)=\sum_{j=4}^{5}\binom{n}{j}p^jq^{n-j}\] \[P(E)=\binom{5}{4}\frac{1}{2}^4\frac{1}{2}^{5-4}+\binom{5}{5}\frac{1}{2}^5\frac{1}{2}^{5-5}\] \[P(E)=5\cdot\frac{1}{16}\cdot\frac{1}{2}+\frac{1}{32}=\frac{5}{32}+\frac{1}{32}=\frac{3}{16}\]Suppose we have a biased coin, with $P(H)=0.7$, and we are going to flip it $5$ times. What is the probability of getting at least $4$ heads?
Intuitively, since the coin is biased towards heads we expect the probability of getting at least $4$ heads in $5$ flips to be larger than using the fair coin, which was$\frac{3}{16}\approx0.19$.
Let us use equation \eqref{6} to find out.
\[P(E)=\sum_{j=4}^{5}\binom{n}{j}p^jq^{n-j}\] \[P(E)=\binom{5}{4}0.7^40.3^{5-4}+\binom{5}{5}0.7^50.3^{5-5}=0.53\]Indeed, as expected, the probability of getting at least $4$ heads in $5$ flips using the biased coin is much larger than using the fair coin.
