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.
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.
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 .
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: