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 steps and the th step can be done in ways, then the entire process can be completed in different ways. Permutations 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 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: 180px