Combinatorics

Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. In particular, it is concerned with "counting" the objects in those collections (enumerative combinatorics), with deciding when the criteria can be met and then constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), with finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and with finding algebraic structures these objects may have (algebraic combinatorics).

Enumerative combinatorics

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.

Related Topics:
Set - Combination - Subset - Permutation - Sequence - Permutations and combinations

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

More generally, given an infinite collection of finite sets {Si} 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 Sn 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 Si will usually have a relatively simple combinatorial description, and little additional structure.

Related Topics:
Natural number - Mathematical problem

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

The simplest such functions are closed formulas, which can be expressed as a composition of simple functions like 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!.

Related Topics:
Closed formula - Factorial

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Integer - Fibonacci number

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:f(n) = rac{phi^{n+2}}{sqrt{5}} - rac{(1-phi)^{n+2}}{sqrt{5}}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where φ = (1 + √5) / 2, the golden mean. However, given that we are looking at a counting function, the presence of the √5 in the result may be considered unaesthetic. As an alternative that shows more clearly why f(n) is a positive integer, f(n) may be expressed by the recurrence

Related Topics:
Golden mean - Recurrence

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:f(n) = f(n-1) + f(n-2).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:f(n) sim rac{phi^{n+2}}{sqrt{5}}

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

as n becomes large.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

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

Related Topics:
Formal power series - Generating function - Ordinary generating function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sum f(n) x^n

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

or the exponential generating function

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

:sum f(n) rac{x^n}{n!},

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

where the sums are taken over the range 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.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~