GetWiki
combinatorics
ARTICLE SUBJECTS
being →
database →
ethics →
fiction →
history →
internet →
language →
linux →
logic →
method →
news →
policy →
purpose →
religion →
science →
software →
truth →
unix →
wiki →
ARTICLE TYPES
essay →
feed →
help →
system →
wiki →
ARTICLE ORIGINS
critical →
forked →
imported →
original →
combinatorics
please note:
- the content below is remote from Wikipedia
- it has been imported raw for GetWiki
{{distinguish|Combinatoriality}}Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many applications ranging from logic to statistical physics, from evolutionary biology to computer science, etc. To fully understand the scope of combinatorics requires a great deal of further amplification, the details of which are not universally agreed upon.WEB, Igor, Pak, What is Combinatorics?, //www.math.ucla.edu/~pak/hidden/papers/Quotes/Combinatorics-quotes.htm, 1 November 2017, According to H. J. Ryser, a definition of the subject is difficult because it crosses so many mathematical subdivisions.{{harvnb|Ryser|1963|loc=p. 2}} In so far as an area can be described by the types of problems it addresses, combinatorics is involved with - the content below is remote from Wikipedia
- it has been imported raw for GetWiki
- the enumeration (counting) of specified structures, sometimes referred to as arrangements or configurations in a very general sense, associated with finite systems,
- the existence of such structures that satisfy certain given criteria,
- the construction of these structures, perhaps in many ways, and
- optimization, finding the "best" structure or solution among several possibilities, be it the "largest", "smallest" or satisfying some other optimality criterion.
History
missing image!
- Plain-bob-minor 2.png -
An example of change ringing (with six bells), one of the earliest nontrivial results in graph theory.
Basic combinatorial concepts and enumerative results appeared throughout the ancient world. In the 6th century BCE, ancient Indian physician Sushruta asserts in Sushruta Samhita that 63 combinations can be made out of 6 different tastes, taken one at a time, two at a time, etc., thus computing all 26 − 1 possibilities. Greek historian Plutarch discusses an argument between Chrysippus (3rd century BCE) and Hipparchus (2nd century BCE) of a rather delicate enumerative problem, which was later shown to be related to SchrÃ¶derâ€“Hipparchus numbers.Stanley, Richard P.; "Hipparchus, Plutarch, SchrÃ¶der, and Hough", American Mathematical Monthly 104 (1997), no. 4, 344â€“350.Habsieger, Laurent; Kazarian, Maxim; and Lando, Sergei; "On the Second Number of Plutarch", American Mathematical Monthly 105 (1998), no. 5, 446. In the Ostomachion, Archimedes (3rd century BCE) considers a tiling puzzle.In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. The Indian mathematician MahÄvÄ«ra (c. 850) provided formulae for the number of permutations and combinations,{{MacTutor | id=Mahavira}}{{Citation |last=Puttaswamy |first=Tumkur K. |contribution= The Mathematical Accomplishments of Ancient Indian Mathematicians |editor-last=Selin |editor-first=Helaine |title=Mathematics Across Cultures: The History of Non-Western Mathematics |publisher=Kluwer Academic Publishers |location=Netherlands |url=https://books.google.com/books?id=2hTyfurOH8AC&printsec=frontcover#v=onepage&q&f=false |year=2000 |isbn=978-1-4020-0260-1 |page=417 }} and these formulas may have been familiar to Indian mathematicians as early as the 6th century CE.JOURNAL, Biggs, Norman L., 1979, The Roots of Combinatorics, Historia Mathematica, 6, 109â€“136, 10.1016/0315-0860(79)90074-0, The philosopher and astronomer Rabbi Abraham ibn Ezra (c. 1140) established the symmetry of binomial coefficients, while a closed formula was obtained later by the talmudist and mathematician Levi ben Gerson (better known as Gersonides), in 1321.{{citation|title=Probability Theory: A Historical Sketch|first=L. E.|last=Maistrov|publisher=Academic Press|year=1974|isbn=9781483218632|url=https://books.google.com/books?id=2ZbiBQAAQBAJ&pg=PA35|page=35}}. (Translation from 1967 Russian ed.)The arithmetical triangleâ€” a graphical diagram showing relationships among the binomial coefficientsâ€” was presented by mathematicians in treatises dating as far back as the 10th century, and would eventually become known as Pascal's triangle. Later, in Medieval England, campanology provided examples of what is now known as Hamiltonian cycles in certain Cayley graphs on permutations.White, Arthur T.; "Ringing the Cosets", American Mathematical Monthly, 94 (1987), no. 8, 721â€“746; White, Arthur T.; "Fabian Stedman: The First Group Theorist?", American Mathematical Monthly, 103 (1996), no. 9, 771â€“778.During the Renaissance, together with the rest of mathematics and the sciences, combinatorics enjoyed a rebirth. Works of Pascal, Newton, Jacob Bernoulli and Euler became foundational in the emerging field. In modern times, the works of J. J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) helped lay the foundation for enumerative and algebraic combinatorics. Graph theory also enjoyed an explosion of interest at the same time, especially in connection with the four color problem.In the second half of the 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject.See Journals in Combinatorics and Graph Theory In part, the growth was spurred by new connections and applications to other fields, ranging from algebra to probability, from functional analysis to number theory, etc. These connections shed the boundaries between combinatorics and parts of mathematics and theoretical computer science, but at the same time led to a partial fragmentation of the field.- Plain-bob-minor 2.png -
An example of change ringing (with six bells), one of the earliest nontrivial results in graph theory.
Approaches and subfields of combinatorics
Enumerative combinatorics
missing image!
- Catalan 4 leaves binary tree example.svg|320px|right|thumb|Five binary trees on three vertices, an example of Catalan numberCatalan numberEnumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. 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. Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.
Combinatorics on words deals with formal languages. It arose independently within several branches of mathematics, including number theory, group theory and probability. It has applications to enumerative combinatorics, fractal analysis, theoretical computer science, automata theory and linguistics. While many applications are new, the classical Chomskyâ€“SchÃ¼tzenberger hierarchy of classes of formal grammars is perhaps the best-known result in the field.- Catalan 4 leaves binary tree example.svg|320px|right|thumb|Five binary trees on three vertices, an example of Catalan numberCatalan numberEnumerative combinatorics is the most classical area of combinatorics and concentrates on counting the number of certain combinatorial objects. 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. Fibonacci numbers is the basic example of a problem in enumerative combinatorics. The twelvefold way provides a unified framework for counting permutations, combinations and partitions.
Analytic combinatorics
Analytic combinatorics concerns the enumeration of combinatorial structures using tools from complex analysis and probability theory. In contrast with enumerative combinatorics, which uses explicit combinatorial formulae and generating functions to describe the results, analytic combinatorics aims at obtaining asymptotic formulae.Partition theory
Partition3D.svg|150px|right|thumb|A plane partitionplane partitionPartition theory studies various enumeration and asymptotic problems related to integer partitions, and is closely related to q-series, special functions and orthogonal polynomials. Originally a part of number theory and analysis, it is now considered a part of combinatorics or an independent field. It incorporates the bijective approach and various tools in analysis and analytic number theory, and has connections with statistical mechanics.Graph theory
Petersen1 tiny.svg|thumb|150px|Petersen graphPetersen graphGraphs 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?). Although there are very strong connections between graph theory and combinatorics, these two are sometimes thought of as separate subjects.Sanders, Daniel P.; 2-Digit MSC Comparison {{webarchive|url=https://web.archive.org/web/20081231163112weblink |date=2008-12-31 }} This is due to the fact that while combinatorial methods apply to many graph theory problems, the two are generally used to seek solutions to different problems.Design theory
Design theory is a study of combinatorial designs, which are collections of subsets with certain intersection properties. Block designs are combinatorial designs of a special type. This area is one of the oldest parts of combinatorics, such as in Kirkman's schoolgirl problem proposed in 1850. The solution of the problem is a special case of a Steiner system, which systems play an important role in the classification of finite simple groups. The area has further connections to coding theory and geometric combinatorics.Finite geometry
Finite geometry is the study of geometric systems having only a finite number of points. Structures analogous to those found in continuous geometries (Euclidean plane, real projective space, etc.) but defined combinatorially are the main items studied. This area provides a rich source of examples for design theory. It should not be confused with discrete geometry (combinatorial geometry).Order theory
Hasse diagram of powerset of 3.svg|thumb|right|150px|Hasse diagram of the powerset of {x,y,z} ordered by inclusion.]]Order theory is the study of partially ordered sets, both finite and infinite. Various examples of partial orders appear in algebra, geometry, number theory and throughout combinatorics and graph theory. Notable classes and examples of partial orders include lattices and Boolean algebras.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. Matroid theory was introduced by Hassler Whitney and studied as a part of order theory. It is now an independent field of study with a number of connections with other parts of combinatorics.Extremal combinatorics
Extremal combinatorics studies extremal questions on set systems. 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. Often it is too hard even to find the extremal answer f(n) exactly and one can only give an asymptotic estimate.Ramsey theory is another part of extremal combinatorics. It states that any sufficiently large configuration will contain some sort of order. It is an advanced generalization of the pigeonhole principle.Probabilistic combinatorics
Self avoiding walk.svg|thumb|right|150px|Self-avoiding walk in a square grid graph.]]In probabilistic combinatorics, the questions are of the following type: what is the probability of a certain property for a random discrete object, such as a random graph? For instance, 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. This approach (often referred to as the probabilistic method) proved highly effective in applications to extremal combinatorics and graph theory. A closely related area is the study of finite Markov chains, especially on combinatorial objects. Here again probabilistic tools are used to estimate the mixing time.Often associated with Paul ErdÅ‘s, who did the pioneering work on the subject, probabilistic combinatorics was traditionally viewed as a set of tools to study problems in other parts of combinatorics. However, with the growth of applications to analysis of algorithms in computer science, as well as classical probability, additive and probabilistic number theory, the area recently grew to become an independent field of combinatorics.Algebraic combinatorics
Young diagram for 541 partition.svg|thumb|right|150px|Young diagram of a partition (5,4,1).]]Algebraic combinatorics is an area of mathematics that employs methods of abstract algebra, notably group theory and representation theory, in various combinatorial contexts and, conversely, applies combinatorial techniques to problems in algebra. Algebraic combinatorics is continuously expanding its scope, in both topics and techniques, and can be seen as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant.Combinatorics on words
Morse-Thue sequence.gif -Geometric combinatorics
missing image!
- Icosahedron.svg|150px|thumb|right|An icosahedronicosahedronGeometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. We should note that combinatorial geometry is an old fashioned name for discrete geometry.
- Icosahedron.svg|150px|thumb|right|An icosahedronicosahedronGeometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, how many faces of each dimension a convex polytope can have. Metric properties of polytopes play an important role as well, e.g. the Cauchy theorem on the rigidity of convex polytopes. Special polytopes are also considered, such as permutohedra, associahedra and Birkhoff polytopes. We should note that combinatorial geometry is an old fashioned name for discrete geometry.
Topological combinatorics
Collier-de-perles-rouge-vert.svg|150px|thumb|right|Splitting a necklace with two cuts.]]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. It should not be confused with combinatorial topology which is an older name for algebraic topology.Arithmetic combinatorics
Arithmetic combinatorics arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive number theory (sometimes also called additive combinatorics) refers to the special case when only the operations of addition and subtraction are involved. One important technique in arithmetic combinatorics is the ergodic theory of dynamical systems.Infinitary combinatorics
Infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. It is a part of set theory, an area of mathematical logic, but uses tools and ideas from both set theory and extremal combinatorics.Gian-Carlo Rota used the name continuous combinatoricsContinuous and profinite combinatorics to describe geometric probability, since there are many analogies between counting and measure.Related fields
Kissing-3d.png -Combinatorial optimization
Combinatorial optimization is the study of optimization on discrete and combinatorial objects. It started as a part of combinatorics and graph theory, but is now viewed as a branch of applied mathematics and computer science, related to operations research, algorithm theory and computational complexity theory.Coding theory
Coding theory started as a part of design theory with early combinatorial constructions of error-correcting codes. The main idea of the subject is to design efficient and reliable methods of data transmission. It is now a large field of study, part of information theory.Discrete and computational geometry
Discrete geometry (also called combinatorial geometry) also began as a part of combinatorics, with early results on convex polytopes and kissing numbers. With the emergence of applications of discrete geometry to computational geometry, these two fields partially merged and became a separate field of study. There remain many connections with geometric and topological combinatorics, which themselves can be viewed as outgrowths of the early discrete geometry.Combinatorics and dynamical systems
Combinatorial aspects of dynamical systems is another emerging field. Here dynamical systems can be defined on combinatorial objects. See for example graph dynamical system.Combinatorics and physics
There are increasing interactions between combinatorics and physics, particularly statistical physics. Examples include an exact solution of the Ising model, and a connection between the Potts model on one hand, and the chromatic and Tutte polynomials on the other hand.See also
- Combinatorial biology
- Combinatorial chemistry
- Combinatorial data analysis
- Combinatorial game theory
- Combinatorial group theory
- List of combinatorics topics
- Phylogenetics
Notes
{{reflist}}References
- BjÃ¶rner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
- BÃ³na, MiklÃ³s; (2011); A Walk Through Combinatorics (3rd Edition). {{ISBN|978-981-4335-23-2}}, {{ISBN|978-981-4460-00-2}}(pbk)
- Graham, Ronald L.; Groetschel, Martin; and LovÃ¡sz, LÃ¡szlÃ³; eds. (1996); Handbook of Combinatorics, Volumes 1 and 2. Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. {{ISBN|0-262-07169-X}}
- Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (October 31, 1997). {{ISBN|0-8493-3986-3}}.
- {{citation|first=John|last=Riordan|author-link=John Riordan (mathematician)|origyear= 1958|year=2002|title=An Introduction to Combinatorial Analysis|publisher=Dover|isbn=978-0-486-42536-8}}
- {{citation|first=Herbert John|last=Ryser|title=Combinatorial Mathematics|series=The Carus Mathematical Monographs(14)|year=1963|publisher=The Mathematical Association of America}}
- Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. {{ISBN|0-521-55309-1}}, {{ISBN|0-521-56069-1}}
- van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd Edition, Cambridge University Press. {{ISBN|0-521-80340-3}}
External links
{{Sister project links| wikt=combinatorics | commons=Category:Combinatorics | b=no | n=no | q=Combinatorics | s=no | v=no | voy=no | species=no | d=no}}- {{springer|title=Combinatorial analysis|id=p/c023250}}
- Combinatorial Analysis â€“ an article in EncyclopÃ¦dia Britannica Eleventh Edition
- Combinatorics, a MathWorld article with many references.
- Combinatorics, from a MathPages.com portal.
- The Hyperbook of Combinatorics, a collection of math articles links.
- The Two Cultures of Mathematics by W. T. Gowers, article on problem solving vs theory building.
- "Glossary of Terms in Combinatorics"
- List of Combinatorics Software and Databases
- content above as imported from Wikipedia
- "combinatorics" does not exist on GetWiki (yet)
- time: 12:28pm EDT - Sun, Jun 24 2018
- "combinatorics" does not exist on GetWiki (yet)
- time: 12:28pm EDT - Sun, Jun 24 2018
[ this remote article is provided by Wikipedia ]
LATEST EDITS [ see all ]
GETWIKI 09 MAY 2016
GetMeta:About
GetWiki
GetWiki
GETWIKI 18 OCT 2015
M.R.M. Parrott
Biographies
Biographies
GETWIKI 20 AUG 2014
GetMeta:News
GetWiki
GetWiki
GETWIKI 19 AUG 2014
GETWIKI 18 AUG 2014
Wikinfo
Culture
Culture
© 2018 M.R.M. PARROTT | ALL RIGHTS RESERVED