FACTOID # 29: 73.3% of America's gross operating surplus in motion picture and sound recording industries comes from California.

 Home Encyclopedia Statistics States A-Z Flags Maps FAQ About

 WHAT'S NEW RELATED ARTICLES People who viewed "Combinatorics" also viewed:

SEARCH ALL

Search encyclopedia, statistics and forums:

(* = Graphable)

Encyclopedia > 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 such as 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). Broadly speaking, pure mathematics is mathematics motivated entirely for reasons other than application. ... Look up discrete in Wiktionary, the free dictionary. ... In mathematics, a set is called finite if there is a bijection between the set and some set of the form {1, 2, ..., n} where is a natural number. ... Euclid, Greek mathematician, 3rd century BC, as imagined by by Raphael in this detail from The School of Athens. ... Algebra is a branch of mathematics concerning the study of structure, relation and quantity. ... Probability theory is the branch of mathematics concerned with analysis of random phenomena. ... In mathematics, a measure-preserving transformation T on a probability space is said to be ergodic if the only measurable sets invariant under T have measure 0 or 1. ... Calabi-Yau manifold Geometry (Greek Î³ÎµÏ‰Î¼ÎµÏ„ÏÎ¯Î±; geo = earth, metria = measure) is a part of mathematics concerned with questions of size, shape, and relative position of figures and with properties of space. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... Statistical physics, one of the fundamental theories of physics, uses methods of statistics in solving physical problems. ... Combinatorial enumeration is a subfield of enumeration that deals with the counting of objects whose symmetries do not exist or, if they exist, are combinatorial in nature. ... Combinatorial design theory is the part of combinatorial mathematics that deals with the existence and construction of systems of finite sets whose intersections have specified numerical properties. ... In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence (hence independence structure) that generalizes linear independence in vector spaces. ... Extremal combinatorics is a field of combinatorics, which is itself a part of mathematics. ... Combinatorial optimization is a branch of optimization in applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory. ... Algebra is a branch of mathematics concerning the study of structure, relation and quantity. ...

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. This is a list of combinatorics topics, by Wikipedia page. ... A pictorial representation of a graph In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. ...

A trivial 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 about 8.0658 × 1067. For factorial rings in mathematics, see unique factorisation domain. ...

Another example of a more difficult 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.

Main article: Permutations

### Permutation with repetition

When order matters and an object can be chosen more than once then 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.

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) The bagua (Chinese: &#20843;&#21350;; pinyin: ; Wade-Giles: pa kua; literally eight trigrams) is a fundamental philosophical concept in ancient China. ...

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.

### Permutation without repetition

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. For factorial rings in mathematics, see unique factorisation domain. ...

Note that if n = r (meaning number of chosen elements is equal to 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 because 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.

An alternative notation is nPr where n stands for the total number of objects, and the r stands for the number of objects that will be chosen. For example, if you have 10 shapes in a bag and you will pick 4 of them out, the notation would be: 10 P 4. This notation is often used on calculators.

## Combinations

Main article: Combinations

In combinatorial mathematics, a combination of members of a set is a subset. ...

### 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 In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ...

${nchoose r} = {{n!} over {r!(n - r)!}}$

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. Just as with permutations, there is an alternate notation used primarily on calculators, of the form nCr.

### Combination with repetition

Main article: Multiset#Multiset coefficients

When the order does not matter and an object can be chosen more than once, then the number of combinations is In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ...

${{(n + r - 1)!} over {r!(n - 1)!}} = {{n + r - 1} choose {r}} = {{n + r - 1} choose {n - 1}}$

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 types of donuts (n) on a menu to choose from and you want three donuts (r) there are (10 + 3 − 1)! / 3!(10 − 1)! = 220 ways to choose (see also multiset). In mathematics, a multiset (sometimes also called a bag) differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member, or perhaps how many memberships it has in the multiset. ...

## 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. In mathematics, a natural number can mean either an element of the set {1, 2, 3, ...} (i. ... A mathematical problem is a problem that can be solved with the help of mathematics. ...

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. In mathematics, an equation or system of equations is said to have a closed-form solution just in case a solution can be expressed analytically in terms of a bounded number of well_known operations. ... For factorial rings in mathematics, see unique factorisation domain. ...

For example, let f(n) be the number of distinct subsets of the set $S(n)={1,2,3, ldots ,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 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:

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

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: Drawing of Leonardo Pisano Leonardo of Pisa or Leonardo Pisano (c. ... A tiling with squares whose sides are successive Fibonacci numbers in length A Fibonacci spiral, created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling shown above â€“ see golden spiral. ... In mathematics, a recurrence relation, also known as a difference equation, is an equation which defines a sequence recursively: each term of the sequence is defined as a function of the preceding terms. ... In mathematics, an equation or system of equations is said to have a closed-form solution if, and only if, at least one solution can be expressed analytically in terms of a bounded number of well-known operations. ...

$f(n) = frac{phi^{n+2}-(1-phi)^{n+2}}{sqrt{5}}$

where $phi = (1 + sqrt 5) / 2$, the golden ratio. // Articles with similar titles include Golden mean (philosophy), the felicitous middle between two extremes, and Golden numbers, an indicator of years in astronomy and calendar studies. ...

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 $nrightarrow$infinity. In this case, we write $f(n) sim g(n),$. In the above example, an asymptotic approximation to f(n) is: The infinity symbol âˆž in several typefaces. ...

$f(n) sim frac{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 In mathematics, formal power series are devices that make it possible to employ much of the analytical machinery of power series in settings that do not have natural notions of convergence. They are also useful to compactly describe sequences and to find closed formulas for recursively defined sequences; this is... In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ... In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

$sum_{nge 0} f(n) x^n$

or the exponential generating function In mathematics a generating function is a formal power series whose coefficients encode information about a sequence an that is indexed by the natural numbers. ...

$sum_{n ge 0} f(n) frac{x^n}{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.

Enumerative combinatorics is used frequently in computer science, because counting a set can closely correspond to computing the elements of a set. Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ...

### Set sizes motivate a naming convention

Various straightforward results from enumerative combinatorics motivate the notations for corresponding types of set theoretical constructions. This very useful convention exploits the natural (semantic and notational) connections between a set S and its cardinality |S|. It likely originates by analogy from the symbol A × B for the Cartesian product of sets A and B and the fact that |A × B| is precisely the (arithmetic) product |A| · |B|. Other examples of this size-of notation include X + Y for the disjoint union of sets X and Y, XY for the set of all functions from X to Y, the special case 2S for the power set of a set S, and the binomial-coefficient notation ${S choose k}$ for the set of all k-element subsets of S. One example where this convention does not seem to have been used yet is X! for the set of all permutations of X, which is the ground set for the symmetric group denoted SX or Sym(X). Set theory is the mathematical theory of sets, which represent collections of abstract objects. ... In mathematics, the cardinality of a set is a measure of the number of elements of the set. There are two approaches to cardinality â€“ one which compares sets directly using bijections and injections, and another which uses cardinal numbers. ... In mathematics, the Cartesian product is a direct product of sets. ... In set theory, a disjoint union (or discriminated union) is a union of a collection of sets whose members are pairwise disjoint. ... Graph of example function, The mathematical concept of a function expresses the intuitive idea of deterministic dependence between two quantities, one of which is viewed as primary (the independent variable, argument of the function, or its input) and the other as secondary (the value of the function, or output). A... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ... In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ... A is a subset of B If X and Y are sets and every element of X is also an element of Y, then we say or write: X is a subset of (or is included in) Y; X &#8838; Y; Y is a superset of (or includes) X; Y...

## 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. Look up theorem in Wiktionary, the free dictionary. ... A partition of U into 6 blocks: an Euler diagram representation. ... In combinatorial mathematics, an ordered partition O of a set S is a sequence A1, A2, A3, ..., An of subsets of S, with union is S, which are non-empty, and pairwise disjoint. ... This is a list of partition topics, in the mathematical sense. ... This is a list of combinatorics topics, by Wikipedia page. ...

### Design theory

A simple result in the block design 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. In combinatorial mathematics, a block design (more fully, a balanced incomplete block design) is a particular kind of set system, which has long-standing applications to experimental design (an area of statistics) as well as purely combinatorial aspects. ... A prime power is a positive integer power of a prime. ... In mathematics, a square number, sometimes also called a perfect square, is a positive integer that can be written as the square of some other integer. ... The Bruckâ€“Chowlaâ€“Ryser theorem is a result on the combinatorics of block designs. ... In abstract algebra, a finite field or Galois field (so named in honor of Ã‰variste Galois) is a field that contains only finitely many elements. ... In mathematics, a quadratic form is a homogeneous polynomial of degree two in a number of variables. ...

When such a structure does exist, it is called a finite projective plane; thus showing how finite geometry and combinatorics intersect. Projective plane - Wikipedia, the free encyclopedia /**/ @import /skins-1. ... A finite geometry is any geometric system that has only a finite number of points. ...

### Ramsey theory

Ramsey theory states that any sufficiently large random configuration will contain some sort of order. Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear. ... In mathematics, the phrase sufficiently large is used in contexts such as: is true for sufficiently large which is actually shorthand for: there exists an such that is true for all . ...

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. Frank Plumpton Ramsey (February 22, 1903 â€“ January 19, 1930) was a British mathematician who, in addition to mathematics, made significant contributions in philosophy and economics. ...

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. In combinatorics, Ramseys theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. ... The inspiration for the name of the principle: pigeons in holes. ...

### 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. In combinatorial mathematics, a matroid is a structure that captures the essence of a notion of independence that generalizes linear independence in vector spaces. ... Calabi-Yau manifold Geometry (Greek Î³ÎµÏ‰Î¼ÎµÏ„ÏÎ¯Î±; geo = earth, metria = measure) is a part of mathematics concerned with questions of size, shape, and relative position of figures and with properties of space. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ... In linear algebra, a family of vectors is linearly independent if none of them can be written as a linear combination of finitely many other vectors in the collection. ...

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. Around 300 BC, the Greek mathematician Euclid laid down the rules of what has now come to be called Euclidean geometry, which is the study of the relationships between angles and distances in space. ... Two intersecting planes in three-dimensional space In mathematics, a plane is a two-dimensional manifold or surface that is perfectly flat. ... In mathematics, particularly in combinatorics, the binomial coefficient of the natural number n and the integer k is the number of combinations that exist. ...

## 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 ST, 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. In mathematics, the concept of hypergraph generalizes the notion of a graph. ... Look up Complement in Wiktionary, the free dictionary. ...

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. In mathematics and applications, particularly the analysis of algorithms, asymptotic analysis is a method of classifying limiting behaviour, by concentrating on some trend. ...

Wikimedia Commons has media related to:
Combinatorics
Look up combinatorics in Wiktionary, the free dictionary.

Image File history File links Commons-logo. ... The Wikimedia Commons (also called Wikicommons) is a repository of free content images, sound and other multimedia files. ... Wikipedia does not have an article with this exact name. ... Wiktionary (a portmanteau of wiki and dictionary) is a multilingual, Web-based project to create a free content dictionary, available in over 150 languages. ... In mathematics, a combinadic is an ordered integer partition, or composition. ... A combinatorial auction is an auction in which bidders can place bids on combinations of items, or â€œpackages,â€ rather than just individual items. ... Combinatorial chemistry involves the rapid synthesis and/or the computer simulation of a large number of different but structurally related molecules. ... In cryptanalysis, a brute force attack on a cipher is a brute-force search of the key space; that is, testing all possible keys, in an attempt to recover the plaintext used to produce a particular ciphertext. ... In proving results in combinatorics several useful combinatorial rules or combinatorial principles are used. ... The factorial based radix or factoradic is a factorial based mixed radix numeral scheme: radix: 5! 4! 3! 2! 1! decimal: 120 24 6 2 1 In this numbering system, the rightmost digit may be 0 or 1, the next 0, 1, or 2, and so on. ... The fundamental theorem of combinatorial enumeration is a theorem in combinatorics that solves the enumeration problem of labelled and unlabelled combinatorial classes. ... In combinatorial mathematics, the inclusion-exclusion principle (also known as the sieve principle) states that if A1, ..., An are finite sets, then where |A| denotes the cardinality of the set A. For example, taking n = 2, we get a special case of double counting: in words, we can count the... This is a list of combinatorics topics, by Wikipedia page. ... This is a list of important publications in mathematics, organized by field. ... In enumerative combinatorial mathematics, identities are sometimes established by arguments that rely on singling out one distinguished element of a set. ... Musical set theory is an atonal or post-tonal method of musical analysis and composition which is based on explaining and proving musical phenomena, taken as sets and subsets, using mathematical rules and notation and using that information to gain insight to compositions or their creation. ...

## References

• Bjorner, A. and Stanley, R.P., A Combinatorial Miscellany
• 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

Results from FactBites:

 Combinatorics - Wikipedia, the free encyclopedia (2347 words) Combinatorics is a branch of mathematics that studies collections (usually finite) of objects that satisfy specified criteria. Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth 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.
More results at FactBites »

Share your thoughts, questions and commentary here