Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. Combinatorial techniques are applicable to many areas of mathematics, and a knowledge of combinatorics is necessary to build a solid command of statistics. It involves the enumeration, combination, and permutation of sets of elements and the mathematical relations that characterize their properties.

Aspects of combinatorics include: counting the structures of a given kind and size, deciding when certain criteria can be met, and constructing and analyzing objects meeting the criteria. Aspects also include finding "largest," "smallest," or "optimal" objects, studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems.

Combinatorial Rules and Techniques

Several useful combinatorial rules or combinatorial principles are commonly recognized and used. Each of these principles is used for a specific purpose. The rule of sum (addition rule), rule of product (multiplication rule), and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets have the same number of elements. Double counting is a method of showing that two expressions are equal. The pigeonhole principle often ascertains the existence of something or is used to determine the minimum or maximum number of something in a discrete context. Generating functions and recurrence relations are powerful tools that can be used to manipulate sequences, and can describe if not resolve many combinatorial situations. Each of these techniques is described in greater detail below.

Rule of Sum

The rule of sum is an intuitive principle stating that if there are $a$ possible ways to do something, and $b$ possible ways to do another thing, and the two things can't both be done, then there are $a + b$ total possible ways to do one of the things. More formally, the sum of the sizes of two disjoint sets is equal to the size of the union of these sets.

Rule of Product

The rule of product is another intuitive principle stating that if there are $a$ ways to do something and $b$ ways to do another thing, then there are $a \cdot b$ ways to do both things.

Inclusion-Exclusion Principle

The inclusion-exclusion principle is a counting technique that is used to obtain the number of elements in a union of multiple sets. This counting method ensures that elements that are present in more than one set in the union are not counted more than once. It considers the size of each set and the size of the intersections of the sets. The smallest example is when there are two sets: the number of elements in the union of $A$ and $B$ is equal to the sum of the number of elements in $A$ and $B$, minus the number of elements in their intersection. See the diagram below for an example with three sets.

Inclusion-Exclusion Principle

Inclusion–exclusion illustrated for three sets

Bijective Proof

A bijective proof is a proof technique that finds a bijective function $f: A \rightarrow B$ between two finite sets $A$ and $B$, which proves that they have the same number of elements, $|A| = |B|$. A bijective function is one in which there is a one-to-one correspondence between the elements of two sets. In other words, each element in set $B$ is paired with exactly one element in set $A$. This technique is useful if we wish to know the size of $A$, but can find no direct way of counting its elements. If $B$ is more easily countable, establishing a bijection from $A$ to $B$ solves the problem. 

Double Counting

Double counting is a combinatorial proof technique for showing that two expressions are equal. This is done by demonstrating that the two expressions are two different ways of counting the size of one set. In this technique, a finite set $X$ is described from two perspectives, leading to two distinct expressions for the size of the set. Since both expressions equal the size of the same set, they equal each other.

Pigeonhole Principle

The pigeonhole principle states that if $a$ items are each put into one of $b$ boxes, where $a>b$, then at least one of the boxes contains more than one item. This principle allows one to demonstrate the existence of some element in a set with some specific properties. For example, consider a set of three gloves. In such a set, there must be either two left gloves or two right gloves (or three of left or right). This is an application of the pigeonhole principle that yields information about the properties of the gloves in the set.

Generating Function

Generating functions can be thought of as polynomials with infinitely many terms whose coefficients correspond to the terms of a sequence. The (ordinary) generating function of a sequence $a_n$ is given by:

 $\displaystyle f(x) = \sum_{n=0}^{\infty} a_{n}x^{n}$

whose coefficients give the sequence $\left \{ a_{0}, a_{1}, a_{2}, ... \right \}$.

Recurrence Relation

A recurrence relation defines each term of a sequence in terms of the preceding terms. In other words, once one or more initial terms are given, each of the following terms of the sequence is a function of the preceding terms. 

The Fibonacci sequence is one example of a recurrence relation. Each term of the Fibonacci sequence is given by $F_{n} = F_{n-1} + F_{n-2}$, with initial values $F_{0}=0$ and $F_{1}=1$. Thus, the sequence of Fibonacci numbers begins: 

$\displaystyle 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...$