Combinatorics

Combinatorics is a branch of pure mathematics concerning the study of discrete (and usually finite) objects. It is related to many other areas of mathematics, such as algebra, probability theory, ergodic theory and geometry, as well as to applied subjects in computer science and statistical physics. Aspects of combinatorics include "counting" the objects satisfying certain criteria (enumerative combinatorics), deciding when the criteria can be met, and constructing and analyzing objects meeting the criteria (as in combinatorial designs and matroid theory), finding "largest", "smallest", or "optimal" objects (extremal combinatorics and combinatorial optimization), and 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 (see the page List of combinatorics topics for details of the more recent development of the subject). One of the oldest and most accessible parts of combinatorics is graph theory, which also has numerous natural connections to other areas.

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.

An example of a simple combinatorial question is the following: What is the number of possible orderings of a deck of 52 distinct playing cards? The answer is 52! (52 factorial), which is equal to about 8.0658 × 1067.

Combinatorics is used frequently in computer science to obtain estimates on the number of elements of certain sets. A mathematician who studies combinatorics is often referred to as a combinatorialist or combinatorist.

Contents

History of combinatorics

Earliest uses

The appearance of the Fibonacci number five in prosody. There is one way to arrange one beat, two for two, three for three, and five for four beats.

The earliest books about combinatorics are from India. A Jain text, the Bhagabati Sutra, had the first mention of a combinatorics problem; it asked how many ways one could take six tastes one, two, or three tastes at a time. The Bhagabati Sutra was written around 300 BC, and thus was the first book to mention the choice function[1]. The next ideas of Combinatorics came from Pingala, who was interested in prosody. Specifically, he wanted to know how many ways a six-syllable meter could be made from short and long notes. He wrote this problem in the Chanda sutra (also Chandahsutra) in the second century BC[2][3]. In addition, he also found the number of meters that had n long notes and k short notes, which is equivalent to finding the binomial coefficients.

The ideas of the Bhagabati were generalised by the Indian mathematician Mahariva in 850 AD, and Pingala's work on prosody was expanded by Bhaskara [1][4] and Hemacandra in 1100 AD. Bhaskara was the first known person to find the generalised choice function, although Brahmagupta may have known earlier[5]. Hemacandra asked how many meters existed of a certain length if a long note was considered to be twice as long as a short note, which is equivalent to finding the Fibonacci numbers[2].

A hexagram

While India was the first nation to publish results on Combinatorics, there were discoveries by other nations on similar topics. The earliest known connection to Combinatorics comes from the Rhind papyrus, problem 79, for the implementation of a geometric series. The next milestone is held by the I Ching. The book is about what different hexagrams mean, and to do this they needed to know how many possible hexagrams there were. Since each hexagram is a permutation with repetitions of six lines, where each line can be one of two states, solid or dashed, combinatorics yields the result that there are 2 6 = 64 hexagrams. A monk also may have counted the number of configurations to a game similar to Go around 700 AD[6]. Although China had relatively few advancements in enumerative combinatorics, they solved a combinatorial design problem, the magic square, around 100 AD[5].

In Greece, Plutarch wrote that the Xenocrates discovered the number of different syllables possible in the Greek language. This, however, is unlikely because this is one of the few mentions of Combinatorics in Greece. The number they found, 1.002 × 10 12 also seems too round to be more than a guess[6][7].

Magic squares remained an interest of China, and they began to generalise their original 3×3 square between 900 and 1300 AD. China corresponded with the Middle East about this problem in the 13th century[5]. The Middle East also learned about binomial coefficients from Indian work, and found the connection to polynomial expansion[8].

Combinatorics in the West

Combinatorics came to Europe in the 13th century through two mathematicians, Leonardo Fibonacci and Jordanus de Nemore. Fibonacci's Liber Abaci introduced many of the Arabian and Indian ideas to Europe, including that of the Fibonacci numbers[9][10]. Jordanus was the first person to arrange the binomial coefficients in a triangle, as he did in proposition 70 of De Arithmetica. This was also done in the Middle East in 1265, and China around 1300[5]. Today, this triangle is known as Pascal's triangle.

Pascal's contribution to the triangle that bears his name comes from his work on formal proofs about it, in addition to his connection between it and probability[5]. Together with Leibniz and his ideas about partitions in the 17th century[11], they are considered the founders of modern combinatorics.

Both Pascal and Leibniz understood that algebra and combinatorics corresponded (aka, binomial expansion was equivalent to the choice function). This was expanded by De Moivre, who found the expansion of a multinomial[12]. De Moivre also found the formula for derangements using the principle of inclusion-exclusion, a method different from Nikolaus Bernoulli, who had found them previously[5]. He managed to approximate the binomial coefficients and factorial. Finally, he found a closed form for the Fibonacci numbers by inventing generating functions[13][14].

In the 18th century, Euler worked on problems of combinatorics. In addition to working on several problems of probability which link to combinatorics, he worked on the knights tour, Graeco-Latin square, Eulerian numbers, and others. He also invented graph theory by solving the Seven Bridges of Königsberg problem, which also led to the formation of topology. Finally, he broke ground with partitions by the use of generating functions[15].

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 shown below, 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.

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

\sum_{n\ge 1} f(n) x^n

or the exponential generating function

\sum_{n \ge 1} f(n) \frac{x^n}{n!}.

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 f(n)/g(n)\rightarrow 1 as n\rightarrowinfinity. In this case, we write f(n) \sim g(n).\,

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.

Permutations with repetitions

When the order matters, and an object can be chosen more than once, the number of permutations is

n^r \,\!

where n is the number of objects from which you can choose and r is the number to be chosen. This assumes objects have an equal chance of being chosen (1/n).

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)

  1. order matters (e.g., A-B is different from B-A, both are included as possibilities)
  2. 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.

Remember, that the permutation formulas only calculate the number of needed ways or combinations in cases, for which, only the order matters and not the components. The following formula looks like this:

{n\choose r_1, r_2, r_3} = {{n!}\over {r_1!r_2!r_3!}}

where n is the total number of components and r1, r2 ... rn are the numbers of repetitions of each of the components in your data.

As a practical example of this, we may want to see in how many ways can we rearrange the following row of letters: A, A, B, B, C. First of all we have to write out all the repetitions:

r_1 = 2, r_2 = 2, r_3 = 1 \,

where r1, r2, r3 are the number of repetitions of A's, B's and a C respectively. The total number of letters is 5, so our n = 5. Applying the formula we get the following:

{n\choose r_1, r_2, r_3} = {5! \over 2!2!1!} = {120 \over 4} = 30.

The total number of ways in which we can rearrange the given row of letters is 30 ways. Due to the large number of arrangements, it would be quite hard to write out the arrangements by hand, as it was done in the example above.

Permutations without repetitions

When the order matters and each object can be chosen only once, then the number of permutations is

(n)_r = \frac{n!}{(n-r)!}

where n is the number of objects from which you can choose, r is the number to be chosen and "!" is the standard symbol meaning factorial. For example, if you have five people and are going to choose three out of these, you will have 5!/(5 − 3)! = 60 permutations.

Note that if n = r (meaning the number of chosen elements is equal to the number of elements to choose from; five people and pick all five) then the formula becomes

\frac{n!}{(n-n)!} = \frac{n!}{0!} = n!

where 0! = 1.

For example, if you have the same five people and you want to find out how many ways you may arrange them, it would be 5! or 5 × 4 × 3 × 2 × 1 = 120 ways. The reason for this is that you can choose from 5 for the initial slot, then you are left with only 4 to choose from for the second slot etc. Multiplying them together gives the total of 120.

As a second, very easy, example we may want to see in how many ways we may rearrange the three letters A, B, C. Using the given above combinatorial formula for permutations without repetitions we have 3! or 3 × 2 × 1 = 6 ways. If we check the following on practice, try to rearrange the letters by hand, we have the following combinations: ABC, ACB, BCA, BAC, CAB, CBA.

If, for instance, the three letters were A, A, B, then the number of combinations will be different and we would have to use a different combinatorial formula, the formula for permutations with repetitions.

Combinations without repetitions

When the order does not matter and each object can be chosen only once, the number of combinations is the binomial coefficient:

{n\choose k} = {{n!} \over {k!(n - k)!}}

where n is the number of objects from which you can choose and k 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. The binomial coefficient is also used to calculate the number of permutations in a lottery.

As a second example of how to use this particular combinatorial formula, we may want to see in how many ways we can produce 4 distinguishable groups of people, each of which consists of 5 people, out of total of 20 people. Remember that in this case the only important thing to us are the components of groups and not the order, in which people appear in those 4 separate groups. The answer to this problem is going to be a very large number. Calculating all the possible combinations we get the following:

{C^{20}_5 = {20\choose 5} = {{20!} \over {{5!}{15!}}} = {{1860480} \over {120}} = {15504}}.

The above formula gives the total ways to choose the first group of 5 people from the original 20. The second group of 5 people will be chosen from the remaining 15, so the formula for that is:

{C^{15}_5 = {15\choose 5} = {{15!} \over {{5!}{10!}}} = {{360360} \over {120}} = {3003}}.

Likewise, the third group of 5 people will be chosen from the remaining 10, so the formula is:

{C^{10}_5 = {10\choose 5} = {{10!} \over {{5!}{5!}}} = {{30240} \over {120}} = {252}}.

Finally, there is only one way to choose the last group of 5 people (there are only 5 people left!).

Multiplying these four numbers yields the total number of combinations: 15504 * 3003 * 252 * 1 = 11,732,745,024.

As it was expected the number of ways, in which, we can organize 4 groups, each consisting of 5 people, out of total of 20 people, is a very large number of combinations. If the groups are not distinguishable, then this must be divided by {4!} to remove the dependence on order of the group assignments.

Combinations with repetitions

Main articles: Multiset#Multiset coefficients and Stars and bars (probability)

When the order does not matter and an object can be chosen more than once, then the number of combinations is

{{(n + k - 1)!} \over {k!(n - 1)!}} = {{n + k - 1} \choose {k}} = {{n + k - 1} \choose {n - 1}}

where n is the number of objects from which you can choose and k is the number to be chosen.

For example, if you have ten types of donuts (n) on a menu to choose from and you want three donuts (k) there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also multiset).

Fibonacci numbers

Let f(n) be the number of distinct subsets of the set S(n) = {1, 2, 3, ..., n} 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 ƒ(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 ƒ(n − 2) of the desired subsets that contain element n. The number of subsets that do not contain n is simply ƒ(n − 1). Adding these numbers together, we get the recurrence relation:

f(n) = f(n-1) + f(n-2)\, ,

where ƒ(1) = 2 and ƒ(2) = 3.

As early as 1202, Leonardo Fibonacci studied these numbers. They are now called Fibonacci numbers; in particular, ƒ(n) is known as the (n + 2)th 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:

f(n) = \frac{\varphi^{n+2}-(1-\varphi)^{n+2}}{\sqrt{5}}

where \varphi = (1 + \sqrt 5) / 2, the golden ratio.

In the above example, an asymptotic approximation to ƒ(n) is:

f(n) \sim \frac{\varphi^{n+2}}{\sqrt{5}}

as n becomes large.

Structural combinatorics

Graph theory

See main article on Graph Theory.

Graphs are basic objects in combinatorics. The questions range from counting (e.g. the number of graphs on n vertices with k edges) to structural (e.g. which graphs contain Hamiltonian cycles) to algebraic questions (e.g. given a graph G and two numbers x and y, does the Tutte polynomial TG(x,y) have a combinatorial interpretation?). It should be noted that while there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects.

Design theory

A example in the block design area of combinatorics is the problem of forming sets.

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.

This 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.

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

\binom{n}{2}.

Is there a set that generates exactly one fewer plane? (No, in almost all cases.) These are extremal questions in geometry, as discussed below.

Extremal and probabilistic 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.

Ramsey theory

Ramsey theory is a celebrated part of extremal combinatorics. It states that any sufficiently large random configuration will contain some sort of order.

Frank P. Ramsey proved that for every integer k there is an integer n, such that every graph on n vertices either contains a clique or an independent set of size k. This is a special case of Ramsey's theorem. For example, 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. The key to the proof in this case is the Pigeonhole Principle: either A knows three of the remaining people, or A does not know three of the remaining people.

Here is a simple proof: Take any one of the six people, call them 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.

Extremal combinatorics

See main article on Extremal combinatorics.

The types of questions addressed in this case are about the largest possible graph which satisfies certain properties. For example, the largest triangle-free graph on 2n vertices is a complete bipartite graph Kn,n.

Probabilistic combinatorics

Here the questions are of the following type: what is the probability of a certain graph property for a random graph (within a certain class) E.g. what is the average number of triangles in a random graph? Probabilistic methods are also used to determine the existence of combinatorial objects with certain prescribed properties (for which explicit examples might be difficult to find), simply by observing that the probability of randomly selecting an object with those properties is greater than 0.

Geometric combinatorics

Geometric combinatorics is related to convex and discrete geometry. It asks, e.g. how many faces of each dimension can a convex polytope have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on rigidity of convex polytopes. Special polytopes are also considered, such as permutohedron, associahedron and Birkhoff polytope.

Topological combinatorics

See main article on Topological combinatorics.

Combinatorial analogs of concepts and methods in topology are used to study graph coloring, fair division, partitions, partially ordered sets, decision trees, necklace problems and discrete Morse theory.

See also

  • Combinadic
  • Combinatorial auction
  • Combinatorial chemistry
  • Combinatorial explosion
  • Combinatorial principles
  • Factoradic
  • Fundamental theorem of combinatorial enumeration
  • Inclusion-exclusion principle
  • List of combinatorics topics
  • List of combinatorists
  • List of publications in mathematics
  • Method of distinguished element
  • Musical set theory

Notes

  1. ↑ 1.0 1.1 "India". Retrieved on 2008-03-05.
  2. ↑ 2.0 2.1 Hall, Rachel (2005-02-16). "Math for Poets and Drummers-The Mathematics of Meter" (PDF). Retrieved on 2008-03-05.
  3. ↑ Kulkarni, Amba. "Recursion and Combinatorial Mathematics in Chandashāstra". Retrieved on 2008-03-04.
  4. ↑ Bhaskara. "The Lilavati of Bhaskara". Brown University. Retrieved on 2008-03-06.
  5. ↑ 5.0 5.1 5.2 5.3 5.4 5.5 Biggs, Norman; Keith Lloyd, Robin Wilson (1995). "44". in Ronald Grahm, Martin Grötschel, László Lovász (Google book). Handbook of Combinatorics. MIT Press. pp. 2163–2188. ISBN 0262571722. http://books.google.com/books?id=kfiv_-l2KyQC&source=gbs_summary_s&cad=0. Retrieved on 2008-03-08. 
  6. ↑ 6.0 6.1 Dieudonné, J.. "The Rhind/Ahmes Papyrus - Mathematics and the Liberal Arts". Historia Math. Truman State University. Retrieved on 2008-03-06.
  7. ↑ Gow, James (1968). A Short History of Greek Mathematics. AMS Bookstore. pp. 71. ISBN 0-828-40218-3. http://books.google.com/books?id=68sYLQa9FuQC&printsec=frontcover. 
  8. ↑ "Middle East". Retrieved on 2008-03-08.
  9. ↑ Devlin, Keith (10 2002). "The 800th birthday of the book that brought numbers to the west". Devlin's Angle. Retrieved on 2008-03-08.
  10. ↑ "Fibonacci Sequence- History". Net Industries (2008). Retrieved on 2008-03-08.
  11. ↑ Dickson, Leonard (2005) [1919]. "Chapter III". Diophantine Analysis. History of the Theory of Numbers. Mineola, New York: Dover Publications, Inc.. pp. 101. ISBN 0-486-44233-0. 
  12. ↑ Hodgson, James; William Derham; Richard Mead (1708) (Google book). Miscellanea Curiosa. Volume II. pp. 183–191. http://books.google.com/books?id=sr04AAAAMAAJ&printsec=titlepage. Retrieved on 2008-03-08. 
  13. ↑ O'Connor, John; Edmund Robertson (06 2004). "Abraham de Moivre". The MacTutor History of Mathematics archive. Retrieved on 2008-03-09.
  14. ↑ Pang, Jong-Shi; Olvi Mangasarian (1999). "10.6 Generating Function". in Jong-Shi Pang (Google book). Computational Optimisation. Volume 1. Netherlands: Kluwer Academic Publishers. pp. 182–183. ISBN 0-792-38480-6. http://books.google.com/books?id=kJa15IMxAoIC&printsec=frontcover#PPA5,M1. Retrieved on 2008-03-09. 
  15. ↑ "Combinatorics and probability". Retrieved on 2008-03-08.

References

External links

Major fields of mathematics
Statistics
Design of experiments
Population • Sampling • Stratified sampling • Replication • Blocking
Sample size estimation
Null hypothesis • Alternative hypothesis • Type I and Type II errors • Statistical power • Effect size
Descriptive statistics
Continuous data
Location
Mean (Arithmetic, Geometric, Harmonic) • Median • Mode
Dispersion
Range • Standard deviation • Coefficient of variation • Percentile
Moments
Variance • Semivariance • Skewness • Kurtosis
Categorical data
Frequency • Contingency table
Inferential statistics
Bayesian inference • Hypothesis testing • Significance • Z-test • Student's t-test • Chi-square test • F-test • P-value • Interval estimation • Maximum likelihood • Minimum distance • Meta-analysis • Confidence interval
Survival analysis
Survival function • Kaplan-Meier • Logrank test • Failure rate • Proportional hazards models
Correlation
Confounding variable • Pearson product-moment correlation coefficient • Rank correlation (Spearman's rank correlation coefficient, Kendall tau rank correlation coefficient)
Linear models
General linear model • Generalized linear model • Analysis of variance • Analysis of covariance
Regression analysis
Linear regression • Nonlinear regression • Logistic regression
Statistical graphics
Bar chart • Biplot • Box plot • Control chart • Forest plot • Histogram • Q-Q plot • Run chart • Scatterplot • Stemplot
History
History of statistics • Founders of statistics • Timeline of probability and statistics
Publications
Journals in statistics • Important publications
Category • Portal • List of topics