Statistics/Probability/Combinatorics

Template:Statistics/Navigation

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 π 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} = (\binom{n}{r})$ .

Note also that $\sum_{r = 0}^{k} (\binom{m}{r}) \times (\binom{n}{k - r}) = (\binom{m + n}{k})$

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

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

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

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

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

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

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

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

Statistics/Probability/Combinatorics

Counting Principle

Permutations

Combinations

Navigation menu

Search