Enumerative combinatorics

From Wikipedia, the free encyclopedia

Enumerative combinatorics or Enumeration is an area of Combinatorics on 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 {S_i} indexed by the natural numbers, 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, many of the problems that arise in applications have a relatively simple combinatorial description. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.

The simplest such functions are closed formulas, which can be expressed as a composition of elementary functions such as factorials, 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, then solve the recurrence to arrive at the desired closed form.

Finally, f(n) may be expressed by a formal power series, called its generating function, 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 approximation may be preferable. A function g(n) is an asymptotic approximation to f(n) 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.

Often the word "enumeration" is used in place of the word "counting" - hence the name "enumerative combinatorics". If "counting" is to mean "repeatedly adding one", then there are counting situations that are not enumeration (e.g. "counting down the days", "counting out cards") and there there are mathematical theorems (for example extremal theorems) about counting that are not enumeration problems, i.e. the problem may not be to enumerate the elements of some pre-given finite set. Enumerative combinatorics is the subbranch of combinatorics (the study of counting) which deals with enumeration. The reason enumeration is so important is the transitivity property for bijections, which makes it easy to build up a general theory. If for three sets A, B and C, we know that A is bijective with B, and we know that B is bijective with C, then we know that A is bijective with C. Thus existing enumeration results can readily be combined to make new ones, and applied in other areas of combinatorics. This combining of results to obtain new ones is not readily available in most other branches of combinatorics.

[edit] See also

• Twelvefold way
• Combinatorial principles
• Fundamental theorem of combinatorial enumeration
• Algebraic combinatorics
• Asymptotic combinatorics
• Combinatorial explosion
• Inclusion-exclusion principle
• Method of distinguished element
• Combinatorial species
• Sieve theory
• Pólya enumeration theorem

[edit] References

• Bjorner, A. and Stanley, R.P., A Combinatorial Miscellany
• Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
• Joseph, George Gheverghese (1994) [1991]. The Crest of the Peacock: Non-European Roots of Mathematics (2nd Edition ed.). London: Penguin Books. ISBN 0-14-012529-9. 
• Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1.
• Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
• Riordan, John (1958). An Introduction to Combinatorial Analysis, Wiley & Sons, New York (republished).
• Riordan, John (1968). Combinatorial identities, Wiley & Sons, New York (republished).

This combinatorics-related article is a stub. You can help Wikipedia by expanding it. v • d • e