## English

### Noun

- a branch of mathematics that studies (usually finite) collections of objects that satisfy specified criteria (see the Wikipedia article for further details)

- a branch of mathematics that studies (usually finite) collections of objects that satisfy specified criteria (see the Wikipedia article for further details)

- Chinese: 组合数学
- Croatian: kombinatorika
- French: combinatoire
- German: Kombinatorik
- Italian: calcolo combinatorio
- Spanish: combinatoria
- Swedish: kombinatorik

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.

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.

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.
## History of Combinatorics

### Earliest uses

The earliest books about combinatorics are
from India. A Jainist 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 . 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 . 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 generalized by
the Indian mathematician Mahariva in 850 AD, and Pingala's work on
prosody was expanded by Bhaskara and Hemacandra in 1100 AD.
Bhaskara was the first known person to find the generalized choice
function, although Brahmagupta may
have known earlier. 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.
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. Although China had relatively few advancements in
enumerative combinatorics, they solved a combinatorial
design problem, the magic
square, around 100 AD.

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 \cdot 10^ also seems too round to be more
than a guess. .

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

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. Together with Leibniz and his ideas
about partitions in the 17th century, 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. De Moivre also found the
formula for derangements using the principle of
inclusion-exclusion, a method different from Nikolaus Bernouli, who
had found them previously. He managed to approximate the binomial
coefficients and factorial.
Finally, he found a closed form for the Fibonacci numbers by
inventing generating
functions.

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.

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_ f(n) x^n

- \sum_ f(n) \frac.

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.

- 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)

- order matters (e.g., 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.

- (n)_ = \frac 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.

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 = \frac = n!

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.

- =

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.

- = =

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

- 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:

- f(n) = \frac

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

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

- f(n) \sim \frac

as n becomes large.

When such a structure does exist, it is called a
finite projective
plane; thus showing how finite
geometry and combinatorics intersect.

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.

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

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.

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

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

- 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.
- The Crest of the Peacock: Non-European Roots of Mathematics
- 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
- Riordan, John (1958). An Introduction to Combinatorial Analysis, Wiley & Sons, New York (republished).
- Riordan, John (1968). Combinatorial identities, Wiley & Sons, New York (republished).

combinatorics in Bulgarian: Комбинаторика

combinatorics in Catalan: Combinatòria
matemàtica

combinatorics in Czech: Kombinatorika

combinatorics in Chuvash: Комбинаторика

combinatorics in Danish: Kombinatorik

combinatorics in German: Kombinatorik

combinatorics in Estonian: Kombinatoorika

combinatorics in Spanish: Combinatoria

combinatorics in Esperanto: Kombinatoriko

combinatorics in Persian: ترکیبیات

combinatorics in French: Combinatoire

combinatorics in Galician: Combinatoria

combinatorics in Korean: 조합론

combinatorics in Indonesian: Kombinatorik

combinatorics in Ido: Kombinatoriko

combinatorics in Icelandic: Talningarfræði

combinatorics in Italian: Calcolo
combinatorio

combinatorics in Hebrew: קומבינטוריקה

combinatorics in Lithuanian: Kombinatorika

combinatorics in Hungarian: Kombinatorika

combinatorics in Dutch: Combinatoriek

combinatorics in Japanese: 組合せ数学

combinatorics in Norwegian: Kombinatorikk

combinatorics in Polish: Kombinatoryka

combinatorics in Portuguese: Combinatória

combinatorics in Romanian: Combinatorică

combinatorics in Russian: Комбинаторика

combinatorics in Simple English:
Combinatorics

combinatorics in Slovak: Kombinatorika

combinatorics in Serbian: Комбинаторна
математика

combinatorics in Finnish: Kombinatoriikka

combinatorics in Swedish: Kombinatorik

combinatorics in Thai:
คณิตศาสตร์เชิงการจัด

combinatorics in Vietnamese: Toán học tổ
hợp

combinatorics in Turkmen: Kombinatorika

combinatorics in Chinese: 组合数学

Privacy Policy,
About Us,
Terms and Conditions,
Contact Us

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2

Material from Wikipedia, Wiktionary, Dict

Valid HTML 4.01 Strict, Valid CSS Level 2.1

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2

Material from Wikipedia, Wiktionary, Dict

Valid HTML 4.01 Strict, Valid CSS Level 2.1