Enumerative combinatorics
More generally, given an infinite collection of finite sets Si indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description.
The twelvefold way provides a unified framework for counting permutations, combinations and partitions.
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.
Some common operation on families of combinatorial objects and its effect on the generating function will now be developed.
In this case it would have the form 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.
A (finite) sequence generalizes the idea of the pair as defined above.
Sequences are arbitrary Cartesian products of a combinatorial object with itself.
The generating function would be: The above operations can now be used to enumerate common combinatorial objects including trees (binary and plane), Dyck paths and cycles.
Binary and plane trees are examples of an unlabeled combinatorial structure.
Trees consist of nodes linked by edges in such a way that there are no cycles.
In plane trees each node can have an arbitrary number of children.
Using the operation on families of combinatorial structures developed earlier, this translates to a recursive generating function: After solving for P(x): An explicit formula for the number of plane trees of size n can now be determined by extracting the coefficient of xn: Note: The notation [xn] f(x) refers to the coefficient of xn in f(x).
The series expansion of the square root is based on Newton's generalization of the binomial theorem.
To get from the fourth to fifth line manipulations using the generalized binomial coefficient is needed.
The expression on the last line is equal to the (n − 1)st Catalan number.
