Enumerative combinatorics

The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, powers, and so on. For instance, as shown below, the number of different possible orderings of a deck of n cards is f(n) = n!. The problem of finding a closed formula is known as algebraic enumeration, and frequently involves deriving a recurrence relation or generating function and using this to arrive at the desired closed form.

Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. In these cases, a simple asymptotic approximation may be preferable. A function ${\displaystyle g(n)}$ is an asymptotic approximation to ${\displaystyle f(n)}$ if ${\displaystyle f(n)/g(n)\to 1}$ as ${\displaystyle n\to \mathrm{\infty }}$. In this case, we write ${\displaystyle f(n)\sim g(n).}$

Generating functions

Generating functions are used to describe families of combinatorial objects. Let ${\displaystyle \mathcal{F}}$ denote the family of objects and let F(x) be its generating function. Then

${\displaystyle F(x)=\sum _{n=0}^{\mathrm{\infty }}{f}_n{x}^n}$

where ${\displaystyle f_n}$ denotes the number of combinatorial objects of size n. The number of combinatorial objects of size n is therefore given by the coefficient of ${\displaystyle x^n}$. Some common operation on families of combinatorial objects and its effect on the generating function will now be developed. The exponential generating function is also sometimes used. In this case it would have the form

${\displaystyle F(x)=\sum _{n=0}^{\mathrm{\infty }}{f}_n\frac{x^n}{n!}}$

Once determined, the generating function yields the information given by the previous approaches. In addition, the various natural operations on generating functions such as addition, multiplication, differentiation, etc., have a combinatorial significance; this allows one to extend results from one combinatorial problem in order to solve others.

Union

Given two combinatorial families, ${\displaystyle \mathcal{F}}$ and ${\displaystyle \mathcal{G}}$ with generating functions F(x) and G(x) respectively, the disjoint union of the two families (${\displaystyle \mathcal{F}\cup \mathcal{G}}$) has generating function F(x) + G(x).

Pairs

For two combinatorial families as above the Cartesian product (pair) of the two families (${\displaystyle \mathcal{F}\times \mathcal{G}}$) has generating function F(x)G(x).

Sequences

A (finite) sequence generalizes the idea of the pair as defined above. Sequences are arbitrary Cartesian products of a combinatorial object with itself. Formally:

${\displaystyle \text{Seq}(\mathcal{F})=ϵ\cup \mathcal{F}\cup \mathcal{F}\times \mathcal{F}\cup \mathcal{F}\times \mathcal{F}\times \mathcal{F}\cup \cdots }$

To put the above in words: An empty sequence or a sequence of one element or a sequence of two elements or a sequence of three elements, etc. The generating function would be:

${\displaystyle 1+F(x)+[F(x){]}^2+[F(x){]}^3+\cdots =\frac{1}{1-F(x)}.}$