Enumerative combinatorics is an area of
combinatorics
Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many a ...
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 is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
s. More generally, given an infinite collection of finite sets ''S''
''i'' indexed by the
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called '' cardinal ...
s, enumerative combinatorics seeks to describe a ''counting function'' which counts the number of objects in ''S''
''n'' for each ''n''. Although
counting the number of elements in a set is a rather broad
mathematical problem
A mathematical problem is a problem that can be 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 ...
, many of the problems that arise in applications have a relatively simple
combinatorial description. The
twelvefold way provides a unified framework for counting
permutation
In mathematics, a permutation of a set is, loosely speaking, an arrangement of its members into a sequence or linear order, or if the set is already ordered, a rearrangement of its elements. The word "permutation" also refers to the act or pro ...
s,
combinations and
partitions
Partition may refer to:
Computing Hardware
* Disk partitioning, the division of a hard disk drive
* Memory partition, a subdivision of a computer's memory, usually for use by a single job
Software
* Partition (database), the division of ...
.
The simplest such functions are ''
closed formula
In mathematics, a closed-form expression is a mathematical expression that uses a finite number of standard operations. It may contain constants, variables, certain well-known operations (e.g., + − × ÷), and functions (e.g., ''n''th roo ...
s'', 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 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 (n-1) \times (n-2) \ ...
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 or
generating function
In mathematics, a generating function is a way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
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 tends to infinity. In projective geometry and related context ...
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 way of encoding an infinite sequence of numbers () by treating them as the coefficients of a formal power series. This series is called the generating function of the sequence. Unlike an ordinary serie ...
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 multiplicative factor in some term of a polynomial, a series, or an expression; it is usually a number, but may be any expression (including variables such as , and ). When the coefficients are themselves ...
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 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 ''A'' and ''B'', denoted ''A''×''B'', is the set of all ordered pairs where ''a'' is in ''A'' and ''b'' is in ''B''. In terms of set-builder notation, that is
: A\t ...
(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 called ...
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 (
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 ; in other words, a number whose '' square'' (the result of multiplying the number by itself, or ⋅ ) is . For example, 4 and −4 are square roots of 16, because .
...
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. Therefore, ''p''
''n'' = ''c''
''n''−1.
See also
*
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 alg ...
*
Asymptotic combinatorics
In combinatorics, the symbolic method is a technique for counting combinatorial objects. It uses the internal structure of the objects to derive formulas for their generating functions. The method is mostly associated with Philippe Flajolet a ...
*
Burnside's lemma
Burnside's lemma, sometimes also called Burnside's counting theorem, the Cauchy–Frobenius lemma, the orbit-counting theorem, or the Lemma that is not Burnside's, is a result in group theory that is often useful in taking account of symmetry when ...
*
Combinatorial explosion
*
Combinatorial game theory
*
Combinatorial principles
*
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 is the university press of the University of Cambridge. Granted letters patent by King Henry VIII in 1534, it is the oldest university press in the world. It is also the King's Printer.
Cambridge University Pr ...
. , .
*
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, books ...
. .
*
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