Enumerative combinatorics

Enumerative combinatorics

Discussion

Encyclopedia
Enumerative combinatorics is an area of combinatorics
Combinatorics
Combinatorics is a branch of mathematics concerning the study of finite or countable discrete structures. 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 ,...

that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an infinite collection of finite sets {Si} indexed by the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...

s, 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
Mathematical problem
A mathematical problem is a problem that is amenable to being represented, analyzed, and possibly solved, with the methods of mathematics. This can be a real-world problem, such as computing the orbits of the planets in the solar system, or a problem of a more abstract nature, such as Hilbert's...

, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way
Twelvefold way
In combinatorics, the twelvefold way is a name given to a systematic classification of 12 related enumerative problems concerning two finite sets, which include the classical problems of counting permutations, combinations, multisets, and partitions either of a set or of a number...

provides a unified framework for counting permutations, combinations and partitions
Partition of a set
In mathematics, a partition of a set X is a division of X into non-overlapping and non-empty "parts" or "blocks" or "cells" that cover all of X...

.

The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorial
Factorial
In mathematics, the factorial of a non-negative integer n, denoted by n!, is the product of all positive integers less than or equal to n...

s, 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!. Often, no closed form is initially available. In these cases, we frequently first derive a recurrence relation
Recurrence relation
In mathematics, a recurrence relation is an equation that recursively defines a sequence, once one or more initial terms are given: each further term of the sequence is defined as a function of the preceding terms....

, then solve the recurrence to arrive at the desired closed form.

Finally, f(n) may be expressed by a formal power series
Formal power series
In mathematics, formal power series are a generalization of polynomials as formal objects, where the number of terms is allowed to be infinite; this implies giving up the possibility to substitute arbitrary values for indeterminates...

, called its generating function
Generating function
In mathematics, a generating function is a formal power series in one indeterminate, whose coefficients encode information about a sequence of numbers an that is indexed by the natural numbers. Generating functions were first introduced by Abraham de Moivre in 1730, in order to solve the general...

, which is most commonly either the ordinary generating function

or the exponential generating function

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
Asymptotic analysis
In mathematical analysis, asymptotic analysis is a method of describing limiting behavior. The methodology has applications across science. Examples are...

approximation may be preferable. A function is an asymptotic approximation to if as . In this case, we write

Once determined, the generating function may allow one to extract all 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.

• Combinatorial principles
Combinatorial principles
In proving results in combinatorics several useful combinatorial rules or combinatorial principles are commonly recognized and used.The rule of sum, rule of product, and inclusion-exclusion principle are often used for enumerative purposes. Bijective proofs are utilized to demonstrate that two sets...

• Fundamental theorem of combinatorial enumeration
Fundamental theorem of combinatorial enumeration
The fundamental theorem of combinatorial enumeration is a theorem in combinatorics that solves the enumeration problem of labelled and unlabelled combinatorial classes.The unlabelled case is based on the Pólya enumeration theorem....

• Algebraic combinatorics
Algebraic combinatorics
Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra....

• Asymptotic combinatorics
• Combinatorial explosion
Combinatorial explosion
In administration and computing, a combinatorial explosion is the rapidly accelerating increase in lines of communication as organizations are added in a process...

• Inclusion-exclusion principle
Inclusion-exclusion principle
In combinatorics, the inclusion–exclusion principle is an equation relating the sizes of two sets and their union...

• Method of distinguished element
Method of distinguished element
In enumerative combinatorial mathematics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set.-Examples:...

• Combinatorial species
Combinatorial species
In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for analysing discrete structures in terms of generating functions. Examples of discrete structures are graphs, permutations, trees, and so on; each of these has an associated generating function...

• Sieve theory
Sieve theory
Sieve theory is a set of general techniques in number theory, designed to count, or more realistically to estimate the size of, sifted sets of integers. The primordial example of a sifted set is the set of prime numbers up to some prescribed limit X. Correspondingly, the primordial example of a...

• Pólya enumeration theorem
Pólya enumeration theorem
The Pólya enumeration theorem , also known as the Redfield–Pólya Theorem, is a theorem in combinatorics that both follows and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. The theorem was first published by John Howard Redfield in 1927...