Combinatorics

Problems include to count the number of such objects (enumerative combinatorics) or whether it contains objects that achieve some maximum (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, 8.065817517094e+67, 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.022e+23, "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. 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.

Let S be a Set with N objects. Combinations of r objects from this set S refer to subsets of S (where the order of listing the elements does not distinguish two subsets). Permutations of r objects from this set S refer to sequences of elements of S' (where two sequences are considered different if they contain the same elements but in a different order).

Links:

• [Avogadro's number]
• [Frank P. Ramsey]

The example above is one of permutations.

back to Mathematics -- Finite Mathematics