Statistics/Probability/Combinatorics

Combinatorics studies permutations and combinations of objects chosen from a sample space. A preliminary knowledge of combinatorics is necessary for a good command of statistics.

Counting Principle

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

Permutations

A permutation is a distinct arrangement of $n$ elements of a set. By the Counting Principle, the number of possible arrangements of $n$ objects in a set is $n\times (n-1)\times (n-2)\times ...\times 1=n!$. What if some of the elements are not distinct? Then, if there are $k$ distinct kinds of elements, the total number of possible arrangements is ${\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 $(n-1)!$.

When faced with very large factorials, a useful approximation is Stirling's formula: $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 ${\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 $n$ elements and take $r$ elements. The number of possible combinations is ${\frac {_{n}P_{r}}{r!}}={\frac {n!}{r!\times (n-r)!}}=_{n}C_{r}=\displaystyle {n \choose r}$.

Note also that $\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:

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

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

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

$(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 $n$, $(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 {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: