| | Combinatorics studies problems involving finite sets of objects that are defined by certain specified properties. For example, the objects in question may themselves be sets, numbers, graphs or other geometrical configurations.
Topological methods, algebraic methods and even probabilistic methods have been used to solve combinatorial problems. Computer algorithms have also been used to solve some seemingly intractable combinatorial problems. Conversely, combinatorial methods have been used successfully to solve problems in many areas of mathematics and computer science. Here is a sample problem that would use combinatorics:
Strangers and Acquaintances (F.P. Ramsey 1930):
What is the least number of people that you need to have in a room so that there is always a group of three mutual strangers or a group of three mutual acquaintances? The answer is six. |
| The use of techniques from algebra, topology, and geometry in the solution of combinatorial problems, or the use of combinatorial methods to attack problems in these areas |
| A a particular ordering of a set of objects. For example, given the set {1, 2, 3}, there are six permutations: {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, and {3, 2, 1}. |
| The number of ways of picking k unordered outcomes from n possibilities. |
| A derangement of n ordered objects, is a permutation in which none of the objects appear in their "natural" (i.e., ordered) place. |
| The factorial n! is defined for a positive integer n as
n! = n*(n-1)*(n-2)...2*1 if n=1,2,...
1 if n=0
|
| A mathematical relationship expressing f(n) as some combination of f(i) with i < n.
|
| A recurrence equation (also called a difference equation) is the discrete analog of a differential equation. A difference equation involves an integer function f(n) in a form like
f(n) - f(n-1) = g(n), (1)
where g is some integer function. |
| Enumerative combinatorics is concerned with counting the number of objects of a certain kind. |
| Extremal combinatorics is concerned with finding the optimal objects of a certain kind. |
| The Ramsey number R(m,n) gives the solution to the party problem, which asks the minimum number of guests R(m,n) that must be invited so that at least m will know each other or at least n will not know each other. |
| A method of solving combinatorial problems by means of an algorithm which is allowed to run forward until a dead end is reached, at which point previous steps are retraced and the algorithm is allowed to run forward again. |
| The partition of space into cells formed by overlaying a collection of surfaces (often hyperplanes). |
| Integers that can be expressed as triangular arrays of dots. They can be characterized by the binomial coefficient C(n,4) (for n > 3).
An explicit formula for the nth triangular number is:
T(n) = n(n+1)/2
|
|