Combinatorics

Combinatorics is a branch of mathematics that studies finite collections of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics) and with deciding whether certain "optimal" objects exist (extremal combinatorics) and which "algebraic" structures these objects have (algebraic combinatorics).

An example of a combinatorial question is the following: What is the number of possible orderings of a deck of 52 playing cards? That number equals 52! (i.e., "fifty-two factorial"). It may seem surprising that this number, about 8.065817517094 × 10⁶⁷, is so large —a little bit more than 8 followed by 67 zeros! Comparing that number to some other large numbers, it is greater than the square of Avogadro's number, 6.022 × 10²³.

Combinatorics came to prominence after the publication of the celebrated Combinatory Analysis by Percy Alexander MacMahon in 1915. One of the most prominent combinatorialists of recent times was Gian-Carlo Rota, who helped formalize the subject beginning in the 1960s. The prolific problem-solver Paul Erdős worked mainly on extremal questions. The study of how to count objects is sometimes thought of separately as the field of enumeration.

Contents

1 Counting functions 2 Results 3 See also 4 References

Counting functions

Calculating the number of ways that certain patterns can be formed is the beginning of combinatorics. Let S be a set with n objects. Combinations of k objects from this set S are subsets of S having k elements each (where the order of listing the elements does not distinguish two subsets). Permutations of k objects from this set S refer to sequences of k different elements of S (where two sequences are considered different if they contain the same elements but in a different order). Formulas for the number of permutations and combinations are readily available and important throughout combinatorics.

More generally, given an infinite collection of finite sets {S_i} typically indexed by the natural numbers, enumerative combinatorics seeks a variety of ways of describing a counting function, f(n), which counts the number of objects in S_n for any n. Although the activity of counting the number of elements in a set is a rather broad mathematical problem, in a combinatorial problem the elements S_i will usually have a relatively simple combinatorial description, and little additional structure.

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, and as noted above, the number of possible different orderings of a deck of n cards is f(n) = n!.

This approach may not always be entirely satisfactory (or practical) for every combinatorial problem. For example, let f(n) be the number of distinct subsets of the integers in the interval [1,n] that do not contain two consecutive integers; thus for example, with n = 4, we have {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, so f(4) = 8. It turns out that f(n) is the n+2 Fibonacci number, which can be expressed in closed form as:

<math>f(n) = \frac{\phi^{n+2}}{\sqrt{5}} - \frac{(1-\phi)^{n+2}}{\sqrt{5}}<math>

where φ = (1 + √5) / 2, the Golden mean. However, given that we are looking at sets of integers, the presence of the √5 in the result may be considered as "unaesthetic" from a combinatoric viewpoint. Alternatively, f(n) may be expressed as the recurrence

<math>f(n) = f(n-1) + f(n-2)<math>

which may be more satisfactory (from a purely combinatorial view), since it more clearly shows why the result is as shown.

Another approach is to find an asymptotic formula

f(n) ~ g(n)

where g(n) is a "familiar" function, and where f(n) approaches g(n) as n approaches infinity. In some cases, a simple asymptotic function may be preferable to a horribly complicated closed formula that yields no insight to the behaviour of the counted objects. In the above example, an asymptotic formula would be

<math>f(n) \sim \frac{\phi^{n+2}}{\sqrt{5}}<math>

as n becomes large.

Finally, and most usefully, f(n) may be expressed by a formal power series, called its generating function, which is most commonly either the ordinary generating function

<math>\sum f(n) x^n<math>

or the exponential generating function

<math>\sum f(n) \frac{x^n}{n!}<math>

where the sums are taken for n ≥ 0. 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.

Results

Some very subtle patterns can be developed and some surprising theorems proved. For example, Frank P. Ramsey proved the following: given any group of six people, it is always the case that one can find three people out of this group that either all know each other, or all do not know each other.

The proof is a short proof by contradiction: suppose the claim is false. This mean that we can have a group of six people such that whenever we look at any three of the six, there are at least two people among these three that know each other and at least two who do not know each other. Consider now one person among the six; call this person "A." Now, among the remaining five people, there must be at least three who either all know A or all do not know A--this is clear since the negation of one condition immediately implies the other condition. Assume first former condition: that at least three of the remaining five know A. Among those three people, at least two of them must know each other, since otherwise we would have three people who all don't know each other, contrary to our hypothesis. But then we have two people who know each other, and know A, and so these two people, along with A, constitute a group of three people among the six who all know each other. This contradicts our initial hypothesis. Assuming that other condition--that three of the remaining five do not know A--results in a similar contradiction. (This is a special case of Ramsey's theorem)

The idea of finding order in random configurations gives rise to Ramsey theory. Essentially this theory says that any sufficiently large configuration will contain at least one instance of some other type of configuration.

See also

• Combinatorial principles
• Inclusion-exclusion principle
• Method of distinguished element
• Important publications in combinatorics
• List of combinatorics topics
• musical set theory
• Infinitary combinatorics

References

• Handbook of Combinatorics, Volumes 1 and 2, R.L. Graham, M. Groetschel and L. Lovász (Eds.), MIT Press, 1996. ISBN 026207169X
• Enumerative Combinatorics, Volumes 1 and 2 (http://www-math.mit.edu/~rstan/ec/), Richard P. Stanley, Cambridge University Press, 1997 and 1999, ISBN 0-521-55309-1Nda:Kombinatorik

de:Kombinatorik es:Combinatoria eo:Kombinatoriko fr:Combinatoire it:Calcolo combinatorio he:קומבינטוריקה lt:Kombinatorika hu:Kombinatorika nl:Combinatoriek pl:Kombinatoryka pt:Combinatória ru:Комбинаторика sk:Kombinatorika sv:Kombinatorik th:คณิตศาสตร์เชิงการจัด vi:Tổ hợp học zh:组合数学