Theory

Theory 1

In many “games of chance,” it is assumed based on symmetry principles that all outcomes are equally likely. From this assumption we infer a rule for the probability measure $P[-]$.

$$P[A]=\frac{|A|}{|S|}$$

In words: the probability of event $A$ is the number of outcomes in $A$ divided by the total number of possible outcomes.

When this formula applies, it is important to be able to count the total outcomes as well as the outcomes that satisfy various conditions.

Permutations

Permutations count the number of ordered lists one can form from a set of items. For a list of $r$ items taken from a total collection of $n$ items, the number of permutations is:

$$P(n,r)=\frac{n!}{(n-r)!}$$

Why is this formula true?

There are $n$ choices for the first item. Then $n-1$ for the second item, after the first has been chosen and removed from the set of possibilities. Then $n-2$ for the third, then …, then $n-r+1$ for the $r^{\text{th}}$ item. So the total number of possibilities is the product:

$$n(n-1)(n-2)\cdots (n-r+1)$$

We can express this with factorials using a technical observation:

$$\begin{array}{c}\frac{n!}{(n-r)!}=\frac{n(n-1)(n-2)\cdots (n-r+1)(n-r)(n-r-1)\cdots 1}{\phantom{n(n-1)(n-2)\cdots (n-r+1)}(n-r)(n-r-1)\cdots 1}\\ \\ \gg \gg n(n-1)(n-2)\cdots (n-r+1)\end{array}$$

Combinations

Combinations count the number of subsets (ignoring order) one can form from some items. For a subset of $r$ items taken from a total collection of $n$ items, the number of combinations is:

$$C(n,r)=\left(\genfrac{}{}{0px}{}{n}{r}\right)=\frac{n!}{r!(n-r)!}$$

This formula can be derived from the formula for permutations.

The set of possible permutations can be partitioned into combinations: each combination determines a subset. By additionally specifying an ordering of the elements in a chosen subset, we obtain a permutation. For a given subset of $r$ elements taken from $n$ items, there are $r!$ ways to determine an ordering of them in a list. Therefore, the number of permutations must be a factor of $r!$ times the number of combinations. (For every combination of size $r$, there are $r!$ ways to order the items in a list.)

The notation $\left(\genfrac{}{}{0px}{}{n}{r}\right)$ is also called the binomial coefficient because it provides the coefficient values of a binomial expansion:

$${(x+y)}^n=\sum _{i=1}^n\left(\genfrac{}{}{0px}{}{n}{i}\right)x^{n-i}{y}^i$$

For example:

$${(x+y)}^4=x^4+4x^{3}y+6x^2{y}^2+4x{y}^3+y^4$$

There are also higher combinations that give multinomial coefficients:

Multinomial coefficient

The general multinomial coefficient is defined by the formula:

$$\left(\genfrac{}{}{0px}{}{n}{r_1,r_2,\dots ,r_k}\right)=\frac{n!}{r_1!r_2!\cdots r_k!}$$

where $r_i\in \mathbb{N}$ and $r_1+r_2+\cdots +r_k=n$.

The multinomial coefficient measures the number of ways to partition $n$ items into subsets with sizes $r_1,r_2,\dots ,r_k$, respectively.

Notice that $\left(\genfrac{}{}{0px}{}{5}{\mathrm{3,2}}\right)=\left(\genfrac{}{}{0px}{}{5}{3}\right)$, so we have already defined these values (i.e. with $k=2$) when we defined binomial coefficients. But when $k>2$, the formula gives new values. They correspond to the coefficients in multinomial expansions. For example, $k=3$ gives the coefficients for ${(x+y+z)}^n$.