Enumerative combinatorics

Enumerative combinatorics is a branch of mathematics focused on counting. It investigates how many ways specific patterns can be formed. Mathematicians often work with an infinite collection of finite sets. These sets are indexed by the natural numbers. The goal is to describe a counting function for each set. This function tells us how many objects exist in a specific set. While counting elements is a broad task, many applications have simple descriptions. For example, the twelvefold way provides a single framework for many problems. This framework helps count permutations, combinations, and partitions all at once.

To solve these problems, mathematicians use different mathematical tools. One tool is a closed formula. This is a composition of elementary functions like factorials or powers. For example, the number of orderings for a deck of $n$ cards is $f(n) = n!$. Finding these formulas is called algebraic enumeration. This process often involves creating a recurrence relation. A recurrence relation is a way to define a value using previous values. Another method is using a generating function. A generating function describes an entire family of combinatorial objects. If $F(x)$ is the function, the number of objects of size $n$ is the coefficient of $x^n$.

Generating functions are very powerful because they allow for specific operations. You can perform addition, multiplication, or differentiation on them. Each operation has a specific combinatorial meaning. For instance, the disjoint union of two families has a generating function that is the sum of their individual functions. If you want to find the Cartesian product of two families, you multiply their generating functions. This is also how you define a pair of objects. You can also create sequences. A sequence is an arbitrary Cartesian product of an object with itself. This allows mathematicians to extend results from one problem to solve another.

Sometimes, finding an exact closed formula is not the best approach. A complex formula might not show how a function behaves as numbers grow. In these cases, mathematicians use an asymptotic approximation. An asymptotic approximation describes the behavior of a function as $n$ approaches infinity. It provides a simpler way to understand the growth of a pattern. This is useful when the exact numbers become too large or complicated to manage. It shifts the focus from exact counts to the general trend of the pattern.

Combinatorial structures are often built from small parts called atoms. These atoms can be either labeled or unlabeled. Labeled atoms are distinct and unique from one another. If you swap two labeled atoms, you create a new object. Unlabeled atoms are indistinguishable from each other. Swapping two unlabeled atoms does not change the object. This distinction is vital when counting different types of structures. Common examples of these structures include Dyck paths, cycles, and various types of trees.

Trees are a major topic in this field. A tree consists of nodes, which act as atoms, linked by edges. These connections must not form any cycles. Most trees have a special node called a root. The root has no parent node. There are different types of trees, such as plane trees and binary trees. In a plane tree, each node can have any number of children. A binary tree is a special case of a plane tree. In a binary tree, every node has either exactly two children or no children at all.

Mathematicians have used these rules to find exact counts for plane trees. A plane tree is defined recursively. It consists of a root node attached to an arbitrary number of subtrees. Each of those subtrees is also a plane tree. By solving the recursive generating function for plane trees, researchers found a specific formula. This formula uses the square root and the generalized binomial theorem. The result shows that the number of plane trees of size $n$ is related to the Catalan numbers. Specifically, the number of plane trees $p_n$ equals the $(n-1)$st Catalan number.