# Statistics/Probability/Combinatorics

## Counting Principle

The Counting Principle is similar to the Multiplicative Principle. If a process involves ${\displaystyle n}$  steps and the ${\displaystyle i}$ th step can be done in ${\displaystyle x_{i}}$  ways, then the entire process can be completed in ${\displaystyle x_{1}\times x_{2}\times ...\times x_{n}}$  different ways.

## Permutations

A permutation is a distinct arrangement of ${\displaystyle n}$  elements of a set. By the Counting Principle, the number of possible arrangements of ${\displaystyle n}$  objects in a set is ${\displaystyle n\times (n-1)\times (n-2)\times ...\times 1=n!}$ . What if some of the elements are not distinct? Then, if there are ${\displaystyle k}$  distinct kinds of elements, the total number of possible arrangements is ${\displaystyle {\frac {n!}{n_{1}!\times n_{2}!\times ...\times n_{k}!}}}$ . What if we are arranging the elements in a circle, rather than a line? Then the number of permutations is ${\displaystyle (n-1)!}$ .

When faced with very large factorials, a useful approximation is Stirling's formula: ${\displaystyle n!\approx {\sqrt {2\pi n}}({\frac {n}{e}})^{n}}$

Now suppose we only choose r distinct elements from the set (without replacement). Then the number of possible permutations becomes ${\displaystyle {\frac {n!}{(n-r)!}}=_{n}P_{r}}$ .

## Combinations

A combination is essentially a subset. It is like a permutation, except with no regard to order. Suppose we have a set of ${\displaystyle n}$  elements and take ${\displaystyle r}$  elements. The number of possible combinations is ${\displaystyle {\frac {_{n}P_{r}}{r!}}={\frac {n!}{r!\times (n-r)!}}=_{n}C_{r}=\displaystyle {n \choose r}}$ .

Note also that ${\displaystyle \sum _{r=0}^{k}\displaystyle {m \choose r}\times \displaystyle {n \choose k-r}=\displaystyle {m+n \choose k}}$

Combinations are found in binomial expansion. Consider the following binomial expansions:

${\displaystyle (x+y)^{1}=x+y}$

${\displaystyle (x+y)^{2}=x^{2}+2xy+y^{2}}$

${\displaystyle (x+y)^{3}=x^{3}+3x^{2}y+3xy^{2}+y^{3}}$

${\displaystyle (x+y)^{4}=x^{4}+4x^{3}y+6x^{2}y^{1}+4xy^{2}+y^{3}}$

As you may have noticed from the above, for any positive integer ${\displaystyle n}$ , ${\displaystyle (x+y)^{n}=\sum _{i=0}^{n}[\displaystyle {n \choose r}\times x^{n-r}\times y^{r}]}$

Another observation from the above is known as Pascal's law. It states that ${\displaystyle \displaystyle {n \choose r}=\displaystyle {n-1 \choose r}+\displaystyle {n-1 \choose r-1}}$

This allows us to construct Pascal's triangle, which is useful for determining combinations: