Combinatorics is a sub-field of mathematics concerned with the science of counting. It’s broadly useful in discrete mathematics and in probability theory.
The basics
For situations that involves us successively making decisions (i.e., sampling from a set of items), we can refer to the rule of products and rule of sums. This holds regardless of how the preceding steps were formed.
The rule of products is given by:
If an operation consists of steps, and the first step can be performed in ways, second in ways, th step in ways, then the entire operation is performed in: , i.e., the intersection of all operations is the product of itself.
From here, we can obviously tell that if , then the operation has possibilities. If we don’t replace an element in the sample space (i.e., we can’t repeat an element), then we have , and the operation has possibilities. We apply the rule of products for the intersection (logical AND) of operations.
The rule of sums tells us that for operations, the union (logical OR) of all operations is the sum of itself.
Permutations and combinations
For problems with simple constraints, we turn to permutations and combinations. We assume for both, that elements in the sample space aren’t replaced.
A permutation is a set of objects where the order of the objects matters. For any and , the number of permutations of a set with elements is elements. The -permutation of a set of elements is an ordered selection of all possible tuples from the set. This is given by:
A combination is a set of objects where the order doesn’t matter (i.e., “abc” is the same as “cab”). The -combination of a set is every possible object multiset given by:
The distinction between permutations and combinations comes down to order. For permutations, we’re comparing ordered tuples of objects. For combinations, we essentially compare multisets.