Combinatorics
From Wikipedia, the free encyclopedia
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, with 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).
Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. One of the oldest and most accessible parts of combinatorics is graph theory which is now connected to other areas.
An example of a combinatorial question is the following: What is the number of possible orderings of a deck of 52 distinct playing cards? The answer is 52! (fifty-two factorial), which is equal to 80,658,175,170,943,878,571,660,636,856,403,766,975,289,505,440,883,277,824,000,000,000,000.
An example of another kind is this problem: Given a certain number n of people, is it possible to assign them to sets so that each person is in at least one set, each pair of people is in exactly one set together, every two sets have exactly one person in common, and no set contains everyone, all but one person, or exactly one person? The answer depends on n. See "Design theory" below.
A mathematician who studies combinatorics is often referred to as a combinatorialist or combinatorist.
Contents |
[edit] Permutations
[edit] Permutation with repetition
When order matters and an object can be chosen more than once then the number of permutations is
where n is the number of objects from which you can choose and r is the number to be chosen.
For example, if you have the letters A, B, C, and D and you wish to discover the number of ways to arrange them in three letter patterns (trigrams)
- order matters (eg. A-B is different from B-A, both are included as possibilities)
- an object can be chosen more than once (A-A possible)
you find that there are 43 or 64 ways. This is because for the first slot you can choose any of the four values, for the second slot you can choose any of the four, and for the final slot you can choose any of the four letters. Multiplying them together gives the total.
[edit] Combinations
[edit] Combination without repetition
When the order does not matter and each object can be chosen only once, the number of combinations is the binomial coefficient
where n is the number of objects from which you can choose and r is the number to be chosen.
For example, if you have ten numbers and wish to choose 5 you would have 10!/(5!(10−5)!) = 252 ways to choose.
[edit] Combination with repetition
When the order does not matter and an object can be chosen more than once, then the number of combinations is
where n is the number of objects from which you can choose and r is the number to be chosen.
For example, if you have three types of donuts (n) on a menu to choose from and you want ten donuts (r) there are (10 + 3 − 1)! / 10!(3 − 1)! = 66 ways to choose (see also multiset).
[edit] Enumerative combinatorics
Counting the number of ways that certain patterns can be formed is the central problem of enumerative combinatorics. Two examples of this type of problem are counting combinations and counting permutations (as discussed in the previous section). More generally, given an infinite collection of finite sets {Si} indexed by the natural numbers, enumerative combinatorics seeks to describe a counting function which counts the number of objects in Sn for each n. Although counting the number of elements in a set is a rather broad mathematical problem, many of the problems that arise in applications have a relatively simple combinatorial description.
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, as noted above, the number of different possible orderings of a deck of n cards is f(n) = n!. Often, no closed form is initially available. In these cases, we frequently first derive a recurrence relation, then solve the recurrence to arrive at the desired closed form. We demonstrate this method below.
For example, let f(n) be the number of distinct subsets of the set 
that do not contain two consecutive integers. When n = 4, we have the sets {}, {1}, {2}, {3}, {4}, {1,3}, {1,4}, {2,4}, so f(4) = 8. We count the desired subsets of S(n) by separately counting those subsets that contain element n and those that do not. If a subset contains n, then it does not contain element n − 1. So there are exactly f(n − 2) of the desired subsets that contain element n. The number of subsets that do not contain n is simply f(n − 1). Adding these numbers together, we get the recurrence relation:
where f(1) = 2 and f(2) = 3.
As early as 1202, Leonardo Fibonacci studied these numbers. They are now called Fibonacci numbers; in particular, f(n) is known as the n + 2nd Fibonacci number. Although the recurrence relation allows us to compute every Fibonacci number, the computation is inefficient. However, by using standard techniques to solve recurrence relations, we can reach the closed form solution:
where 
, the golden ratio.
Often, a complicated closed formula yields little insight into the behavior of the counting function as the number of counted objects grows. In these cases, a simple asymptotic approximation may be preferable. A function g(n) is an asymptotic approximation to f(n) if 
as 
infinity. In this case, we write 
. In the above example, an asymptotic approximation to f(n) is:
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
or the exponential generating function
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.
Enumerative combinatorics is used frequently in computer science, because counting a set can closely correspond to computing the elements of a set.
[edit] Structural combinatorics
There are many combinatorial patterns and theorems related to the structure of combinatoric sets. These often focus on a partition or ordered partition of a set. See the List of partition topics for an expanded list of related topics or the List of combinatorics topics for a more general listing. Some of the more notable results are highlighted below.
[edit] Design theory
A simple result in this area of combinatorics is that the problem of forming sets, described in the introduction, has a solution only if n has the form q2 + q + 1. It is less simple to prove that a solution exists if q is a prime power. It is conjectured that these are the only solutions. It has been further shown that if a solution exists for q congruent to 1 or 2 mod 4, then q is a sum of two square numbers. This last result, the Bruck-Ryser theorem, is proved by a combination of constructive methods based on finite fields and an application of quadratic forms.
When such a structure does exist, it is called a finite projective plane; thus showing how finite geometry and combinatorics intersect.
[edit] Ramsey theory
Ramsey theory states that any sufficiently large random configuration will contain some sort of order.
Frank P. Ramsey proved that, 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.
A simpler and shorter proof: Take any of the six people, call him A. Either A knows three of the remaining people, or A does not know three of the remaining people. Assume the former (the proof is identical if we assume the latter). Let the three people that A knows be B, C, and D. Now either two people from {B,C,D} know each other (in which case we have a group of three people who know each other - these two plus A) or none of B,C,D know each other (in which case we have a group of three people who do not know each other - B,C,D). QED.
This is a special case of Ramsey's theorem. The key to this proof is the use of the Pigeonhole Principle in the statement either A knows three of the remaining people, or A does not know three of the remaining people.
[edit] Matroid theory
Matroid theory abstracts part of geometry. It studies the properties of sets (usually, finite sets) of vectors in a vector space that do not depend on the particular coefficients in a linear dependence relation. Not only the structure but also enumerative properties belong to matroid theory.
For instance, given a set of n vectors in Euclidean space, what is the largest number of planes they can generate? (Answer: the binomial coefficient C(n,3).) Is there a set that generates exactly one less plane? (No, in almost all cases.) These are extremal questions in geometry.
[edit] Extremal combinatorics
Many extremal questions deal with set systems. A simple example is the following: what is the largest number of subsets of an n-element set one can have, if no two of the subsets are disjoint? Answer: half the total number of subsets. Proof: Call the n-element set S. Between any subset T and its complement S − T, at most one can be chosen. This proves the maximum number of chosen subsets is not greater than half the number of subsets. To show one can attain half the number, pick one element x of S and choose all the subsets that contain x.
A more difficult problem is to characterize the extremal solutions; in this case, to show that no other choice of subsets can attain the maximum number while satisfying the requirement.
Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.
[edit] See also
- Combinatorial principles
- Fundamental theorem of combinatorial enumeration
- Inclusion-exclusion principle
- Method of distinguished element
- Important publications in combinatorics
- List of combinatorics topics
- Musical set theory
- Combinatorial chemistry
- Combinatorial explosion
- Combinatorial auction
- Combinadic
- Factoradic
- List of Combinatorists
[edit] References
- Graham, R.L., Groetschel M., and Lovász L., eds. (1996). Handbook of Combinatorics, Volumes 1 and 2. Elsevier (North-Holland), Amsterdam, and MIT Press, Cambridge, Mass. ISBN 0-262-07169-X.
- Joseph, George Gheverghese [1991] (1994). The Crest of the Peacock: Non-European Roots of Mathematics, 2nd Edition, London: Penguin Books. ISBN 0-14-012529-9.
- Katz, Victor J. (1998). A History of Mathematics: An Introduction, 2nd Edition. Addison-Wesley Education Publishers. ISBN 0-321-01618-1.
- Lindner, Charles C. and Christopher A. Rodger (eds.) Design Theory, CRC-Press; 1st. edition (October 31, 1997). ISBN 0-8493-3986-3.
- van Lint, J.H., and Wilson, R.M. (2001). A Course in Combinatorics, 2nd Edition. Cambridge University Press. ISBN 0-521-80340-3.
- O'Connor, John J. and Robertson, Edmund F. (1999-2004). MacTutor History of Mathematics archive. St Andrews University.
- Rashed, R. (1994). The development of Arabic mathematics : between arithmetic and algebra. London.
- Stanley, Richard P. (1997, 1999). Enumerative Combinatorics, Volumes 1 and 2. Cambridge University Press. ISBN 0-521-55309-1, ISBN 0-521-56069-1.
- Combinatorial Analysis – an article in Encyclopædia Britannica Eleventh Edition
|
Major fields of mathematics
|
|---|
| Logic • Set theory • Algebra (Abstract algebra - Linear algebra) • Discrete mathematics • Combinatorics • Number theory • Analysis • Geometry • Topology • Applied mathematics • Probability • Statistics • Mathematical physics |
