combinatorial enumeration
   HOME

TheInfoList



OR:

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 appl ...
that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting
combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s 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 proc ...
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 n ...
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, i.e., determining the size of a set. The traditional way of counting consists of continually increasing a (mental or spoken) counter by a unit for every ele ...
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 an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many ap ...
description. The
twelvefold way In combinatorics, the twelvefold way is 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 ...
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 proc ...
s,
combination In mathematics, a combination is a selection of items from a set that has distinct members, such that the order of selection does not matter (unlike permutations). For example, given three fruits, say an apple, an orange and a pear, there are th ...
s 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 a ...
. 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 ro ...
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) \t ...
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 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 seri ...
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 contexts, ...
approximation may be preferable. A function g(n) is an asymptotic approximation to f(n) if f(n)/g(n)\rightarrow 1 as n\rightarrow \infty. In this case, we write f(n) \sim g(n).\,


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 seri ...
s are used to describe families of combinatorial objects. Let \mathcal denote the family of objects and let ''F''(''x'') be its generating function. Then :F(x) = \sum^_f_nx^n where f_n 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 var ...
of x^n. Some common operation on families of combinatorial objects and its effect on the generating function will now be developed. The
exponential 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 series ...
is also sometimes used. In this case it would have the form :F(x) = \sum^_f_n\frac 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, \mathcal and \mathcal with generating functions ''F''(''x'') and ''G''(''x'') respectively, the
disjoint union In mathematics, a disjoint union (or discriminated union) of a family of sets (A_i : i\in I) is a set A, often denoted by \bigsqcup_ A_i, with an injection of each A_i into A, such that the images of these injections form a partition of A (th ...
of the two families (\mathcal \cup \mathcal) 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\ti ...
(pair) of the two families (\mathcal \times \mathcal) 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 calle ...
generalizes the idea of the pair as defined above. Sequences are arbitrary Cartesian products of a combinatorial object with itself. Formally: :\mbox(\mathcal) = \epsilon\ \cup\ \mathcal\ \cup\ \mathcal \!\times\! \mathcal\ \cup\ \mathcal \!\times\! \mathcal \!\times\! \mathcal\ \cup \cdots 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: :1+F(x) +
(x) An emoticon (, , rarely , ), short for "emotion icon", also known simply as an emote, is a pictorial representation of a facial expression using characters—usually punctuation marks, numbers, and letters—to express a person's feelings, ...
2 +
(x) An emoticon (, , rarely , ), short for "emotion icon", also known simply as an emote, is a pictorial representation of a facial expression using characters—usually punctuation marks, numbers, and letters—to express a person's feelings, ...
3 + \cdots = \frac.


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, including only woody plants with secondary growth, plants that are u ...
(
binary Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two digits (0 and 1) * Binary function, a function that takes two arguments * Binary operation, a mathematical operation that t ...
and plane),
Dyck path In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
s 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 \mathcal denote the family of all plane trees. Then this family can be recursively defined as follows: :\mathcal = \ \times\, \mbox(\mathcal) In this case \ represents the family of objects consisting of one node. This has generating function ''x''. Let ''P''(''x'') denote the generating function \mathcal. 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: :P(x) = x\,\frac After solving for ''P''(''x''): :P(x) = \frac An explicit formula for the number of plane trees of size ''n'' can now be determined by extracting the coefficient of ''x''''n'': : \begin p_n & = ^nP(x) = ^n\frac \\ pt& = ^n\frac - ^n\frac \sqrt \\ pt& = -\frac ^n\sum^_ (-4x)^k \\ pt& = -\frac (-4)^n \\ pt& = \frac \end Note: The notation '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 . E ...
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 In combinatorial mathematics, the Catalan numbers are a sequence of natural numbers that occur in various counting problems, often involving recursively defined objects. They are named after the French-Belgian mathematician Eugène Charles Cata ...
. 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 algeb ...
* Asymptotic combinatorics *
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 In mathematics, a combinatorial explosion is the rapid growth of the complexity of a problem due to how the combinatorics of the problem is affected by the input, constraints, and bounds of the problem. Combinatorial explosion is sometimes used ...
*
Combinatorial game theory Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a ''position'' that the players ...
*
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. B ...
*
Combinatorial species In combinatorial mathematics, the theory of combinatorial species is an abstract, systematic method for deriving the generating functions of discrete structures, which allows one to not merely count these structures but give bijective proofs invol ...
*
Inclusion–exclusion principle In combinatorics, a branch of mathematics, the inclusion–exclusion principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as : , A \cup ...
*
Method of distinguished element In the mathematical field of enumerative combinatorics, identities are sometimes established by arguments that rely on singling out one "distinguished element" of a set. Definition Let \mathcal be a family of subsets of the set A and let x \in ...
*
Pólya enumeration theorem The Pólya enumeration theorem, also known as the Redfield–Pólya theorem and Pólya counting, is a theorem in combinatorics that both follows from and ultimately generalizes Burnside's lemma on the number of orbits of a group action on a set. ...
*
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 prototypical example of a sifted set is the set of prime numbers up to some prescribed lim ...


References

* Zeilberger, Doron
Enumerative 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 Combinatorics

CRC 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 Henry VIII of England, King Henry VIII in 1534, it is the oldest university press A university press is an academic publishing hou ...
. , . * 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