Enumerative combinatorics is an area of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
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
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
s. More generally, given an infinite collection of finite sets ''S''
''i'' indexed by the
natural number
In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
s, enumerative combinatorics seeks to describe a ''counting function'' which counts the number of objects in ''S''
''n'' for each ''n''. Although
counting
Counting is the process of determining the number of elements of a finite set of objects; that is, determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for ever ...
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
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and as an end to obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ...
description. The
twelvefold way provides a unified framework for counting
permutation
In mathematics, a permutation of a set can mean one of two different things:
* an arrangement of its members in a sequence or linear order, or
* the act or process of changing the linear order of an ordered set.
An example of the first mean ...
s,
combinations and
partitions.
The simplest such functions are ''
closed formulas'', which can be expressed as a composition of elementary functions such as
factorial
In mathematics, the factorial of a non-negative denoted is the Product (mathematics), product of all positive integers less than or equal The factorial also equals the product of n with the next smaller factorial:
\begin
n! &= n \times ...
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''!. The problem of finding a closed formula is known as
algebraic enumeration, and frequently involves deriving a
recurrence relation
In mathematics, a recurrence relation is an equation according to which the nth term of a sequence of numbers is equal to some combination of the previous terms. Often, only k previous terms of the sequence appear in the equation, for a parameter ...
or
generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
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
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates Limit of a function#Limits at infinity, tends to infinity. In pro ...
approximation may be preferable. A function
is an asymptotic approximation to
if
as
. In this case, we write
Generating functions
Generating function
In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
s are used to describe families of combinatorial objects. Let
denote the family of objects and let ''F''(''x'') be its generating function. Then
:
where
denotes the number of combinatorial objects of size ''n''. The number of combinatorial objects of size ''n'' is therefore given by the
coefficient
In mathematics, a coefficient is a Factor (arithmetic), multiplicative factor involved in some Summand, term of a polynomial, a series (mathematics), series, or any other type of expression (mathematics), expression. It may be a Dimensionless qu ...
of
. 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
:
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,
and
with generating functions ''F''(''x'') and ''G''(''x'') respectively, the
disjoint union
In mathematics, the disjoint union (or discriminated union) A \sqcup B of the sets and is the set formed from the elements of and labelled (indexed) with the name of the set from which they come. So, an element belonging to both and appe ...
of the two families (
) has generating function ''F''(''x'') + ''G''(''x'').
Pairs
For two combinatorial families as above the
Cartesian product
In mathematics, specifically set theory, the Cartesian product of two sets and , denoted , is the set of all ordered pairs where is an element of and is an element of . In terms of set-builder notation, that is
A\times B = \.
A table c ...
(pair) of the two families (
) has generating function ''F''(''x'')''G''(''x'').
Sequences
A (finite)
sequence
In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...
generalizes the idea of the pair as defined above. Sequences are arbitrary Cartesian products of a combinatorial object with itself. Formally:
:
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:
:
Combinatorial structures
The above operations can now be used to enumerate common combinatorial objects including
trees
In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only p ...
(
binary and plane),
Dyck paths and cycles. A combinatorial structure is composed of atoms. For example, with trees the atoms would be the nodes. The atoms which compose the object can either be labeled or unlabeled. Unlabeled atoms are indistinguishable from each other, while labelled atoms are distinct. Therefore, for a combinatorial object consisting of labeled atoms a new object can be formed by simply swapping two or more atoms.
Binary and plane trees
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. There is generally a node called the root, which has no parent node. In plane trees each node can have an arbitrary number of children. In binary trees, a special case of plane trees, each node can have either two or no children. Let
denote the family of all plane trees. Then this family can be recursively defined as follows:
:
In this case
represents the family of objects consisting of one node. This has generating function ''x''. Let ''P''(''x'') denote the generating function
.
Putting the above description in words: A plane tree consists of a node to which is attached an arbitrary number of subtrees, each of which is also a plane tree. 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 ''x''
''n'':
:
Note: The notation
''n''">'x''''n''''f''(''x'') refers to the coefficient of ''x''
''n'' in ''f''(''x'').
The series expansion of the
square root
In mathematics, a square root of a number is a number such that y^2 = x; in other words, a number whose ''square'' (the result of multiplying the number by itself, or y \cdot y) is . For example, 4 and −4 are square roots of 16 because 4 ...
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
The Catalan numbers are a sequence of natural numbers that occur in various Enumeration, counting problems, often involving recursion, recursively defined objects. They are named after Eugène Charles Catalan, Eugène Catalan, though they were p ...
. Therefore, ''p''
''n'' = ''c''
''n''−1.
See also
*
Algebraic combinatorics
*
Asymptotic combinatorics
*
Burnside's lemma
*
Combinatorial explosion
In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to the way its combinatorics depends on input, constraints and bounds. Combinatorial explosion is sometimes used to justify the intractability of cert ...
*
Combinatorial game theory
Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Research in this field has primarily focused on two-player games in which a ''position'' ev ...
*
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 combinatorics ...
*
Combinatorial species
*
Inclusion–exclusion principle
*
Method of distinguished element
*
Pólya enumeration theorem
*
Sieve theory
References
*
Zeilberger, DoronEnumerative and Algebraic Combinatorics*
Björner, Anders and
Stanley, Richard P.''A Combinatorial Miscellany''*
Graham, Ronald L.,
Grötschel M., and
Lovász, László, eds. (1996). ''Handbook of Combinatorics'', Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. .
*
* Loehr, Nicholas A. (2011).
Bijective CombinatoricsCRC Press , .
*
Stanley, Richard P. (1997, 1999).
''Enumerative Combinatorics'', Volumes 1 and 2 Cambridge University Press
Cambridge University Press was the university press of the University of Cambridge. Granted a letters patent by King Henry VIII in 1534, it was the oldest university press in the world. Cambridge University Press merged with Cambridge Assessme ...
. , .
*
Goulden, Ian P. and
Jackson, David M. (2004).
''Combinatorial Enumeration'' Dover Publications
Dover Publications, also known as Dover Books, is an American book publisher founded in 1941 by Hayward and Blanche Cirker. It primarily reissues books that are out of print from their original publishers. These are often, but not always, book ...
. .
*
Riordan, John (1958). ''An Introduction to Combinatorial Analysis'', Wiley & Sons, New York (republished).
* Riordan, John (1968). ''Combinatorial Identities'', Wiley & Sons, New York (republished).
* {{cite book , last=Wilf , first=Herbert S. , author-link=Herbert Wilf , title=Generatingfunctionology , edition=2nd , location=Boston, MA , publisher=Academic Press , year=1994 , isbn=0-12-751956-4 , zbl=0831.05001 , url=http://www.math.upenn.edu/%7Ewilf/DownldGF.html