Often, in experiments with finite sample spaces, the outcomes are equiprobable. In such cases, the probability of an event amounts to the number of outcomes comprising this event divided by the total number of outcomes in the sample space. While counting outcomes may appear straightforward, it is in many circumstances a daunting task. For example, consider the number of distinct subsets of the integers ${\displaystyle \{1,\dots ,n\}}$ that do not contain two consecutive integers. This number is equal to

${\displaystyle {\frac {\phi ^{n+2}-(1-\phi )^{n+2}}{\sqrt {5}}}}$

where ${\displaystyle \phi ={\frac {1+{\sqrt {5}}}{2}}}$ is the golden ratio. It can also be obtained recursively through the Fibonacci recurrence relation.

Calculating the number of ways that certain patterns can be formed is part of the field of combinatorics. In this section, we introduce useful counting techniques that can be applied to situations pertinent to probability theory.

The Counting Principle

The Fundamental Rule of Counting: If a set of choices or trials, ${\displaystyle T_{1},\dots ,T_{k}}$ , could result, respectively, in ${\displaystyle n_{1},\dots ,n_{k}}$ possible outcomes, the entire set of ${\displaystyle k}$ choices or trials has ${\displaystyle n_{1}\times \cdots \times n_{k}}$ possible outcomes. (The numbers ${\displaystyle n_{1},\dots ,n_{k}}$ cannot depend on which outcomes actually occur.)

By the Fundamental Rule of Counting, the total number of possible sequences of choices is ${\displaystyle 5\times 4\times 3\times 2\times 1=120}$ sequences. Each sequence is called a permutation of the five items. A permutation of items is an ordering of the items. More generally, by the Fundamental Rule of Counting, in ordering ${\displaystyle n}$ things, there are ${\displaystyle n}$ choices for the first, ${\displaystyle n-1}$ choices for the second, etc., so the total number of ways of ordering a total of ${\displaystyle n}$ things is ${\displaystyle n\times (n-1)\times (n-2)\times \cdots \times 3\times 2\times 1}$ . This product is written ${\displaystyle n!}$ , which is pronounced "n-factorial." By convention, ${\displaystyle 0!=1}$

The counting principle is the guiding rule for computing the number of elements in a cartesian product as well.

${\displaystyle S\times T=\{(x,y)|x\in S\land y\in T\}}$

The number of elements in the cartesian product ${\displaystyle S\times T}$ is equal to mn. Note that the total number of outcomes does not depend on the order in which the experiments are realized.

Example

Consider an experiment consisting of flipping a coin and rolling a die. There are two possibilities for the coin, heads or tails, and the die has six sides. The total number of outcomes for this experiment is ${\displaystyle 2\cdot 6=12}$ . That is, there are twelve outcomes for the roll of a die followed by the toss of a coin:

${\displaystyle 1H,1T,2H,2T,3H,3T,4H,4T,5H,5T,6H,6T}$ .

The counting principle can be extended to compute the number of elements in the cartesian product of multiple sets. Consider the finite sets ${\displaystyle S_{1},\dots ,S_{r}}$ and their cartesian product

${\displaystyle S_{1}\times \cdots \times S_{r}=\{(s_{1},\dots ,s_{r})|s_{p}\in S_{p}\}}$

If we denote the cardinality of ${\displaystyle S_{p}}$ by ${\displaystyle n_{p}=|S_{p}|}$ , then the number of distinct ordered r-tuples of the form ${\displaystyle (s_{1},\dots ,s_{r})}$ is ${\displaystyle n=n_{1}\times \cdots \times n_{r}}$ .

Example - Sampling with Replacement and Ordering

An urn contains ${\displaystyle n}$ balls numbered ${\displaystyle 1,\dots ,n}$ . A ball is drawn from the urn, and its number is recorded on an ordered list. The ball is then replaced in the urn. This procedure is repeated ${\displaystyle k}$ times. We wish to compute the number of possible sequences that results from this experiment. There are ${\displaystyle k}$ drawings and n possibilities per drawing. Using the counting principle, we conclude that the number of distinct sequences is ${\displaystyle n^{k}}$ .

Example

The power set of S, denoted by ${\displaystyle 2^{S}}$ , is the set of all subsets of ${\displaystyle S}$ . In set theory, ${\displaystyle 2^{S}}$ represents the set of all functions ${\displaystyle S\to \{0,1\}}$ . By identifying a function in ${\displaystyle 2^{S}}$ with the corresponding preimage of one, we obtain a bijection between ${\displaystyle 2^{S}}$ and the subsets of ${\displaystyle S}$. In particular, each function in ${\displaystyle 2^{S}}$ is the characteristic function of a subset of ${\displaystyle S}$ .

Suppose that ${\displaystyle S}$ is finite with ${\displaystyle n=|S|}$ elements. For every element of ${\displaystyle S}$ , a characteristic function in ${\displaystyle 2^{S}}$ is either 0 or 1. There are therefore ${\displaystyle 2^{n}}$ distinct characteristic functions ${\displaystyle S\to \{0,1\}}$ . Hence, the number of distinct subsets of ${\displaystyle S}$ is given by ${\displaystyle 2^{n}}$ .

Formulae

The formula for counting combinations has special cases that are worth memorizing:

${\displaystyle {\binom {n}{0}}={\binom {n}{n}}=1}$ (There is only one way to pick no thing and only one way to pick all ${\displaystyle n}$ things.)

${\displaystyle {\binom {n}{1}}={\binom {n}{n-1}}=n}$ (there are n ways to pick one thing or to leave one thing out)

${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$ (There are the same number of ways of picking ${\displaystyle k}$ of ${\displaystyle n}$ things as there are of leaving out ${\displaystyle k}$ of ${\displaystyle n}$ things)

Permutations

In this section, we will discuss groups of unique objects where ordering is important.
Permutation: An arrangement of objects without repetition where order is important.
Importance of Order: We say that the order is important when sets ${\displaystyle S}$ and ${\displaystyle S'}$ contain the exact same objects, but in a different order. In this case, we treat them differently. For example, ${\displaystyle S=\{H,T\}}$, and ${\displaystyle S'=\{T,H\}}$ are different.

Example: Find all 2-letter permutations of ${\displaystyle A,B,C,D}$

Solution: Start with the letter ${\displaystyle A}$. It can pair up with ${\displaystyle B}$, ${\displaystyle C}$, or ${\displaystyle D}$, but NOT ${\displaystyle A}$. Therefore, all the two letter permutation that start with ${\displaystyle A}$ are:
${\displaystyle A,B}$
${\displaystyle A,C}$
${\displaystyle A,D}$

Similarly, for B as the starting letter,
${\displaystyle B,A}$
${\displaystyle B,C}$
${\displaystyle B,D}$

Notice that since the order is important, ${\displaystyle A,B}$ and ${\displaystyle B,A}$ are NOT the same thing!

For C,
${\displaystyle C,A}$
${\displaystyle C,B}$
${\displaystyle C,D}$

Finally, for D,
${\displaystyle D,A}$
${\displaystyle D,B}$
${\displaystyle D,C}$

Permutations using all the objects: ${\displaystyle n}$ objects, arranged into group size of ${\displaystyle n}$ without repetition, and order being important. ${\displaystyle P(n,n)=n!}$ Example: Find all permutations of ${\displaystyle A,B,C,D,F,G,H}$ .

Permutations of some of the objects: ${\displaystyle n}$ objects, group size ${\displaystyle k}$ , order is important. ${\displaystyle P(n,k)={\frac {n!}{(n-k)!}}}$ Example: Find all 2-letter combinations using letters ${\displaystyle A,B,C,D,F,G,H}$

Distinguished permutation: if a word has ${\displaystyle n}$ letters, ${\displaystyle k}$ of which are unique, let ${\displaystyle n}$ ${\displaystyle (n_{1},\dots ,n_{k})}$ be the frequency of each of the ${\displaystyle k}$ letters: ${\displaystyle {\frac {n!}{(n_{1}!)(n_{2}!)(n_{3}!)}}}$ .

Consider the integer set ${\displaystyle S=\{1,\dots ,n\}}$ . A permutation of S is an ordered arrangement of its elements, a list without repetitions. The number of permutations of S can be computed as follows. The number of distinct possibilities for the first item is ${\displaystyle n}$ . The number of possibilities for the second item is ${\displaystyle n-1}$ , namely all the integers in ${\displaystyle S}$ except the first element in the list. Similarly, the number of distinct possibilities for the ${\displaystyle m}$-th item is ${\displaystyle n-m+1}$ . This pattern continues until all the elements in ${\displaystyle S}$ are listed. Summarizing, we find that the total number of permutations of ${\displaystyle S}$ is ${\displaystyle n}$-factorial, ${\displaystyle n!=n\times (n-1)\times \cdots \times 2\times 1}$ .

Example

We wish to compute the number of permutations of ${\displaystyle S=\{1,2,3\}}$ . Since the set S contains three elements, it has ${\displaystyle 3!=6}$ permutations. They can be listed as 123, 132, 213, 231, 312, 321.

Combinations

Combinations: arrangement of objects without repetition, where order is NOT important. A combination of n objects, arranged in groups of size r, without repetition, and order being important. C(n, r) = n!/r!(n-r)! Another way to write a combination of n things, r at a time, is using the Binomial notation (Binomial Distribution). Combinations of this type are referred to verbally as "n choose r".

Consider the integer set S = {1, 2, ... , n}. A combination is a subset of S. We emphasize that a combination differs from a permutation in that elements in a combination have no specific ordering. The 2-element subsets of S = {1, 2, 3, 4} are {1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4} , whereas the 2-permutations of S are more numerous with (1, 2), (1, 3), (1, 4), (2, 1), (2, 3), (2, 4), (3, 1), (3, 2), (3, 4), (4, 1), (4, 2), (4, 3) . There are therefore fewer 2-element subsets of S than 2-permutations of S.

We can compute the number of k-element combinations of S = {1, 2, ... , n} as follows. First, we note that a k-permutation can be formed by first selecting k objects from S and then ordering them. There are k! distinct ways of ordering k objects. The number of k-permutations must then equal the number of k-element combinations multiplied by k!. Since the total number of k-permutations of S is n! / (n-k)!, the number of k-element combinations is found to be

${\displaystyle {\frac {n!}{k!(n-k)!}}={\frac {n(n-1)\cdots (n-k+1)}{k!}}.}$

This expression is called a binomial coefficient. Observe that selecting a k-element subset of S is equivalent to choosing the n-k elements that belong to its complement.

Example - Sampling without Replacement or Ordering: An urn contains n balls numbered one through n. A ball is drawn from the urn and placed in a jar. This process is repeated until the jar contains k balls, where ${\displaystyle k\leq n}$. We wish to compute the number of distinct combinations the jar can hold after the completion of this experiment. Because there is no ordering in the jar, this amounts to counting the number of k-element subsets of a given n-element set, which is given by

${\displaystyle {\frac {n!}{k!(n-k)!}}.}$

Again, let S = {1, 2, ... , n}. Since a combination is also a subset and the number of k-element combinations of S is ${\displaystyle {\frac {n!}{k!(n-k)!}}}$, the sum of the binomial coefficients over all values of k must be equal to the number of elements in the power set of S. Thus, we get

${\displaystyle \sum _{k=0}^{n}{\frac {n!}{k!(n-k)!}}=2^{n}.}$

Partitions

Abstractly, a combination is equivalent to partitioning a set into two subsets, one containing k objects and the other containing the n-k remaining objects. In general, the set S = {1, 2, ... , n } can be partitioned into r subsets. Let ${\displaystyle n_{1},n_{2},\ldots ,n_{r}}$ be nonnegative integers such that ${\displaystyle \sum _{p=1}^{r}n_{p}=n.}$

Consider the following iterative algorithm that leads to a partition of S. First, we select a subset of ${\displaystyle n_{1}}$ elements from S. Having chosen the first subset, we select a second subset containing ${\displaystyle n_{2}}$ elements from the remaining ${\displaystyle n-n_{1}}$ elements. We continue this procedure by successively choosing subsets of ${\displaystyle n_{p}}$ elements from the remaining ${\displaystyle n-n_{1}-\cdots -n_{p-1}}$ elements, until no element remains. This algorithm yields a partition of S into r subsets, with the p-th subset containing exactly ${\displaystyle n_{p}}$ elements.

We wish to count the number of such partitions. We know that there are ${\displaystyle {\frac {n!}{n_{1}!(n-n_{1})!}}}$ ways to form the first subset. Examining our algorithm, we see that there are

${\displaystyle {\frac {(n-n_{1}-\cdots -n_{p-1})!}{n_{p}!(n-n_{1}-\cdots -n_{p})!}}}$

ways to form the p-th subset. Using the counting principle, the total number of partitions is then given by

${\displaystyle {\frac {n!}{n_{1}!n_{2}!\cdots n_{r}!}}.}$

This expression is called a multinomial coefficient.

Example: A die is rolled nine times. We wish to compute the number of outcomes for which every odd number appears three times. The number of distinct sequences in which one, three, and five each appear three times is equal to the number of partitions of {1, 2, ... , 9} into three subsets of size three, namely

${\displaystyle {\frac {9!}{3!3!3!}}=1680.}$

In the above analysis, we assume that the size of each subset is fixed, three subsets of size three. Suppose instead that we are interested in counting the number of ways of picking the sizes of the subsets, r subsets of ${\displaystyle n_{1},n_{2},\ldots ,n_{r}}$ size, where the sum of the sizes is a constant. Specifically, we wish to compute the number of ways integers ${\displaystyle n_{1},n_{2},\ldots ,n_{r}}$ can be selected such that every integer is nonnegative and

${\displaystyle \sum _{p=1}^{r}n_{p}=n}$.

We can visualize the number of possible assignments as follows. Picture n balls spaced out on a straight line and consider r-1 vertical markers, each of which can be put between two consecutive balls, before the first ball, or after the last ball. For instance, if there are five balls and two markers then one possible assignement is illustrated below.

The number of objects in the first subset corresponds to the number balls before the first marker. Similarly, the number of objects in the p-th subset is equal to the number of balls between the p-th marker and the preceding one. Finally, the number of objects in the last subset is simply the number of balls after the last marker. In the figure, the integer assignment is

${\displaystyle (n_{1},n_{2},n_{3})=(0,2,3).}$

Two consecutive markers imply that the corresponding subset is empty. There is a natural bijection between an integer assignment and the graphical representation depicted above. To count the number of possible integer assignments, it then suffices to compute the number of ways to position the markers and the balls. In particular, there are n + r - 1 positions, n balls, and r - 1 markers. The number of ways to assign the markers is equal to the number of n-combinations of n + r - 1 elements,

${\displaystyle {\frac {(n+r-1)!}{n!(r-1)!}}.}$

Example - Sampling with Replacement, without Ordering: An urn contains r balls numbered one through r. A ball is drawn from the urn and its number is recorded. The ball is then returned to the urn. This procedure is repeated a total of n times. The outcome of this experiment is a table that contains the number of times each ball has come in sight. We are interested in computing the number of distinct outcomes. This is equivalent to counting the ways a set with n elements can be partitioned into r subsets. The number of possible outcomes is therefore given by

${\displaystyle {\frac {(n+r-1)!}{n!(r-1)!}}.}$

Computing Probabilities

In this section, we present two straightforward applications of combinatorics to computing the probability of winning the lottery.

Example - Pick 3 Texas Lottery: The Texas Lottery game Pick 3 is easy to play. A player must pick three numbers from zero to nine, and choose how to play them: exact order, or any order. The Pick 3 balls are drawn using three air-driven machines. These machines use compressed air to mix and select each ball.

The probability of winning while playing the exact order is

${\displaystyle {\frac {1}{10}}{\frac {1}{10}}{\frac {1}{10}}={\frac {1}{1000}}.}$

The probability of winning while playing any order depends on the numbers selected. If three distinct numbers are selected then the probability of winning is 3/500. If a number is repeated twice, the probability of winning is 3/1000. While, if the same number is selected three times, the probability of winning becomes 1/1000.

Example - Mega Millions Texas Lottery: To play the Mega Millions game, a player must select five numbers from 1 to 56 in the upper white play area of the play board, and one Mega Ball number from 1 to 46 in the lower yellow play area of the play board. All drawing equipment is stored in a secured on-site storage room. Only authorized drawings department personnel have keys to this door. Upon entry of the secured room to begin the drawing process, a lottery drawing specialist examines the security seal to determine if any unauthorized access has occurred. For each drawing, the Lotto Texas balls are mixed by four acrylic mixing paddles rotating clockwise. High speed is used for mixing and low speed for ball selection. As each ball is selected, it rolls down a chute into an official number display area. We wish to compute the probability of winning the Mega Millions Grand Prize, which require the correct selection of the five white balls plus the gold Mega ball. The probability of winning the Mega Millions Grand Prize is

${\displaystyle {\frac {51!5!}{56!}}{\frac {1}{46}}={\frac {1}{175711536}}.}$