# 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[edit]

The Counting Principle is similar to the Multiplicative Principle. If a process involves steps and the th step can be done in ways, then the entire process can be completed in different ways.

## Permutations[edit]

A permutation is a distinct arrangement of elements of a set. By the Counting Principle, the number of possible arrangements of objects in a set is . What if some of the elements are *not* distinct? Then, if there are distinct kinds of elements, the total number of possible arrangements is . What if we are arranging the elements in a circle, rather than a line? Then the number of permutations is .

When faced with very large factorials, a useful approximation is Stirling's formula:

Now suppose we only choose *r* distinct elements from the set (without replacement). Then the number of possible permutations becomes .

## Combinations[edit]

A combination is essentially a subset. It is like a permutation, except with no regard to order. Suppose we have a set of elements and take elements. The number of possible combinations is .

Note also that

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

As you may have noticed from the above, for any positive integer ,

Another observation from the above is known as Pascal's law. It states that

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