| Combinatorics |
Website Links For Combinatorics |
Information AboutCombinatorics |
| CATEGORIES ABOUT COMBINATORICS | |
| combinatorics | |
| discrete mathematicscombinatorics | |
| discrete mathematics | |
| discrete mathematics | |
| SHOPPER'S DELIGHT | |
|
OVERVIEW AND HISTORY 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 part 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 playing cards? That number equals 52! (fifty-two Factorial ). It may seem surprising that this number, about 8.065817517094 × 1067, is so large — 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.022 × 1023. 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 are in exactly one set together, every two sets have exactly one person in common, and no set contains all or all but one of the people? The answer depends on ''n'' and is only partially known to this day. See "Design theory" below for a partial answer. The earliest recorded statements of combinatorical rules appear in India . The Medical treatise ''Sushruta Samhita'' written by Sushruta in the 6th Century BC states that 63 Combination s can be made out of six different tastes – bitter, sour, salty, sweet, astringent, and hot – by taking them one at a time, two at a time, three at a time, etc. In other words, there are 6 single tastes, 15 combinations of two, 20 combinations of three, etc. The ''Bhagabati Sutra'', written by a Jain a mathematician circa 300 BC , contains rules on Combinations And Permutations corresponding to , , , , Numbers are calculated in the cases where n = 2, 3 and 4. The author then says that one can compute the numbers in the same way for larger n: "In this way, 5, 6, 7, ..., 10, etc. or an enumerable, unenumerable or Infinite number of things may be specified. Taking one at a time, two at a time, ... ten at a time, as the number of combinations are formed they must all be worked out." This suggests that the arithmetic can be extended to various infinite numbers. The relation of the number of combinations to the Coefficient s occurring in the Binomial Expansion was noted by Pingala in the 3rd Century BC in a musical composition. He gave the different combinations of ''guru'' and ''laghu'' sounds as a ''meru-prastara'' ( Pascal's Triangle ) and gave a rule simpler than that of Pascal , based on the simple formula Varahamihira in the 6th Century CE states that "if a quantity of 16 substances is varied in four different ways, the result will be 1820." He found this result using rules related to Pascal's triangle. In the 9th Century , Mahavira gave an explicit algorithm for calculating the number of combinations and provided the well-known general formula Muslim Mathematicians later studied combinatorial analysis from at least the 13th Century . Ibn Mun'im , in the Maghreb of North Africa in the early 13th century, dealt with combinatory problems. He stated the rule for determining all possible combinations of ''n'' coulours ''p'' times and established, inductively, the resutling arithmetic triangle of the relationship as He applied similar formulae for permutations with and without repititions using the Arabic alphabet for illustrative purposes. He also does some work on combinatorial reasoning. Persian mathematician Al-Farisi , in the late 13th Century , introduced ideas concerning factorisation and combinatorial methods. Al-Farisi's approach is based on the unique factorisation of an integer into powers of Prime Number s. He states and proves this fundamental theorem of arithmetic. Al-Farisi saw the relation between polygonal numbers and the Binomial Coefficient s and he presented arguments, using an early form of Mathematical Induction , which showed a relation between triangular numbers, the sums of triangular numbers, the sums of the sums of triangular number, etc., and the combinations of ''n'' objects taken ''k'' at a time. Enumerative combinatorics came to prominence in Europe after counting configurations became essential to elementary Probability , starting with the work of Pascal and others from the 17th Century . Modern combinatorics began developing in the late 19th Century and became a distinguishable field of study in the 20th Century , partly through the publication of the systematic enumerative treatise ''Combinatory Analysis'' by Percy Alexander MacMahon in 1915 and the work of R.A. Fisher in Design Of Experiments in the 1920s . Two of the most prominent combinatorialists of recent times were the prolific problem-raiser and problem-solver Paul Erdős , who worked mainly on extremal questions, and Gian-Carlo Rota , who helped to formalize the subject beginning in the 1960s , mostly in enumeration and algebraization. The study of how to count objects is sometimes thought of separately as the field of Enumeration . PERMUTATIONS AND COMBINATIONS
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. Combination s of ''k'' objects from this set ''S'' are Subset s of ''S'' having ''k'' elements each (where the order of listing the elements does not distinguish two subsets). Permutation s of ''k'' objects from this set ''S'' refer to '' Sequence s'' of ''k'' different elements of ''S'' (where two sequences are considered different if they contain the same elements but in a different order, or if they have a different length). Formulas for the number of Permutations And Combinations are readily available and important throughout combinatorics. More generally, given an infinite collection of finite sets {''S''''i''} typically indexed by the Natural Number s, enumerative combinatorics seeks a variety of ways of describing a ''counting function'', ''f''(''n''), which counts the number of objects in ''S''''n'' 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 ''S''''i'' will usually have a relatively simple combinatorial description, and little additional structure. The simplest such functions are '' Closed Formula s'', which can be expressed as a composition of simple functions like Factorial s, 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''!. This approach may not always be entirely satisfactory (or practical). For example, let ''f''(''n'') be the number of distinct subsets of the Integer s in the interval {Link without Title} 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+2''nd Fibonacci Number , ''F''(''n''+2), so it can be expressed in closed form as : where , the Golden Ratio . However, given that we are looking at a counting function, the presence of the 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 Relation '' : with the initial conditions and . Another approach is to find an '' Asymptotic Formula '' : 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 : 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. STRUCTURAL COMBINATORICS There are many combinatorial patterns and Theorem s 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. 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 ''q''2 + ''q'' + 1. It is less simple to prove that a solution exists if ''q'' is a Prime Power , may exist if ''q'' is a sum of two Square Numbers , but cannot exist for any other positive integer ''q''. This last result, the Bruck-Ryser Theorem , is proved by a combination of constructive methods based on Finite Field s and an application of Quadratic Form s. When such a structure does exist, it is called a finite Projective Plane ; thus showing how Finite Geometry and combinatorics intersect. Ramsey Theory 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. The proof is a short Proof By Contradiction : suppose the claim is false. This means that we can have a group of six people such that whenever we look at any three of the six, there are at least two people among these three that know each other and at least two who do not know each other. Consider now one person among the six; call this person "A." Now, among the remaining five people, there must be at least three who either all know A or all do not know A--this is clear since the negation of one condition immediately implies the other condition. Assume first former condition: that at least three of the remaining five know A. Among those three people, at least two of them must know each other, since otherwise we would have three people who all don't know each other, contrary to our hypothesis. But then we have two people who know each other, and know A, and so these two people, along with A, constitute a group of three people among the six who all know each other. This contradicts our initial hypothesis. Assuming that other condition--that three of the remaining five do not know A--results in a similar contradiction. This is a special case of Ramsey's Theorem . The idea of finding order in random configurations gives rise to Ramsey Theory . Essentially this theory says that any Sufficiently Large configuration will contain at least one instance of some other type of configuration. Matroid Theory This part of combinatorics 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 ''C''(''n'',3).) Is there a set that generates exactly one less plane? (No, in almost all cases.) These are extremal questions in geometry. EXTREMAL COMBINATORICS Many extremal questions deal with ''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. SEE ALSO
REFERENCES
|