Combinatorics

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

Combinatorics is a branch of mathematics. It studies finite collections of objects that satisfy certain criteria, and is in particular concerned with counting the objects in those collections (enumerative combinatorics) and with deciding whether certain "optimal" objects exist (extremal 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! (see factorial). It is the product of all the natural numbers from one to fifty-two. It may seem surprising that this number, about 8.065817517094 × 1067, is so large. That is 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 × 1023, "the number of atoms, molecules, etc., in a gram mole".

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.

Some very subtle patterns can be developed and some surprising theorems proved. One example of a surprising theorem is of Frank P. Ramsey:

Suppose 6 people meet each other at a party. Some of those already know each other, some of them do not. It is always the case that one can find 3 people out of the 6 such that they either all know each other or that they are all strangers to each other.

The idea of finding order in random configuration gives rise to Ramsey theory. Essentially this theory says (in mathematical language) that any random configuration will, if it is large enough, contain smaller configuration of a given type. For example if you try hard enough any pattern of stars can be found in the sky. It has been used to debunk claims that some patterns are especially meaningful.

See also: Finite Mathematics


External links: