Combinatorics: Wikis

Advertisements
  
  
  
  

Note: Many of our articles have direct quotes from sources you can cite, within the Wikipedia article! This article doesn't yet, but we're working on it! See more info or our list of citable articles.

Did you know ...


More interesting facts on Combinatorics

Include this on your site/blog:

Encyclopedia

From Wikipedia, the free encyclopedia

Combinatorics is a branch of discrete mathematics concerning the study of finite or countable discrete structures. Aspects of combinatorics include counting the structures of a given kind and size (enumerative combinatorics), deciding when certain 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 studying combinatorial structures arising in an algebraic context, or applying algebraic techniques to combinatorial problems (algebraic combinatorics).

Combinatorial problems arise in many areas of pure mathematics, notably in algebra, probability theory, topology, and geometry,[1] and combinatorics also has many applications in optimization, computer science, ergodic theory and statistical physics. Many combinatorial questions have historically been considered in isolation, giving an ad hoc solution to a problem arising in some mathematical context. In the later twentieth century however powerful and general theoretical methods have been developed, making combinatorics into an independent branch of mathematics in its own right. One of the oldest and most accessible parts of combinatorics is graph theory, which also has numerous natural connections to other areas. Combinatorics is used frequently in computer science to obtain formulas and estimates in the analysis of algorithms.

A mathematician who studies combinatorics is often referred to as a combinatorialist or combinatorist.

Contents

History of combinatorics

An example of change ringing (with six bells and two ringers).

Basic combinatorial concepts and enumerative results have appeared throughout the ancient world. In 6th century BC, 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. Roman historian Plutarch discusses an argument between Chrysippus (3rd century BC) and Hipparchus (2nd century BC) of a rather delicate enumerative problem, which was later shown to be related to Schröder numbers.[2][3] In the Ostomachion, Archimedes (3rd century BC) calculates the number of solutions of a certain tiling puzzle.

In the Middle Ages, combinatorics continued to be studied, largely outside of the European civilization. Notably, an Indian mathematician Mahavira (c. 850) provided the general formulae for the number of permutations and combinations. 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.[4] 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.[5]

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 the modern times, the works by J. J. Sylvester (late 19th century) and Percy MacMahon (early 20th century) laid 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.

Enumerative combinatorics

Five binary trees on three vertices, an example of Catalan numbers.

Enumerative 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

Partition 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, analytic number theory, and has connections with statistical mechanics.

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.[6]

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.

Order theory

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

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 pioneer 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 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. Within the last decade or so, algebraic combinatorics came to be seen more expansively as the area of mathematics where the interaction of combinatorial and algebraic methods is particularly strong and significant. One of the fastest developing subfields within algebraic combinatorics is combinatorial commutative algebra.

Combinatorics on words

Construction of a Thue-Morse infinite word.

Combinatorics on words is an area of combinatorics which studies 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.

Geometric combinatorics

Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. 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 permutohedra, associahedra and Birkhoff polytopes.

Topological combinatorics

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.

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 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 combinatorics[7] to describe probability and measure theory, since there are many analogies between counting and measure.

Related fields

Kissing spheres are connected to both coding theory and discrete geometry.
Advertisements

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. It is now a large field of study, part of information theory.

Discrete and computational geometry

Discrete geometry (also called combinatorial geometry) also began 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.

Phylogenetics

Phylogenetics is an area of mathematical biology that deals with the reconstruction and analysis of phylogenetic (evolutionary) trees and networks based on inherited characteristics. The main graph concepts are trees, X-trees and maximum parsimony trees.

See also

Notes

  1. ^ Björner and Stanley, p. 2
  2. ^ R.P. Stanley, "Hipparchus, Plutarch, Schröder, and Hough", Amer. Math. Monthly 104 (1997), no. 4, 344-350.
  3. ^ L. Habsieger, M. Kazarian, S. Lando, On the second number of Plutarch, Amer. Math. Monthly 105 (1998), no. 5, 446.
  4. ^ History of Combinatorics, chapter in a textbook.
  5. ^ Arthur T. White, ”Ringing the Cosets,” Amer. Math. Monthly 94 (1987), no. 8, 721-746; Arthur T. White, ”Fabian Stedman: The First Group Theorist?,” Amer. Math. Monthly 103 (1996), no. 9, 771-778.
  6. ^ 2-Digit MSC Comparison, by Daniel P. Sanders.
  7. ^ Continuous and profinite combinatorics

References

External links


Study guide

Up to date as of January 14, 2010

From Wikiversity

Crystal Clear app kaddressbook.png
Please help develop this page

This page was created, but so far, little content has been added. Everyone is invited to help expand and create educational content for Wikiversity. If you need help learning how to add content, see the editing tutorial and the MediaWiki syntax reference.

To help you get started with content, we have automatically added references below to other Wikimedia Foundation projects. This will help you find materials such as information, media and quotations on which to base the development of "Combinatorics" as an educational resource. However, please do not simply copy-and-paste large chunks from other projects. You can also use the links in the blue box to help you classify this page by subject, educational level and resource type.

Wikipedia-logo.png Run a search on Combinatorics at Wikipedia.
Commons-logo.svg Search Wikimedia Commons for images, sounds and other media related to: Combinatorics
Wikimedia-logo.svg Search for Combinatorics on the following projects:
Smiley green alien whatface.svg Lost on Wikiversity? Please help by choosing project boxes to classify this resource by:
  • subject
  • educational level
  • resource type
< Wikiversity < Wikiversity:School of Mathematics < School of Mathematics:Statistics

Pigeonhole Principle

The principle can be summarized with the following memorable sentence:

If N pigeons roost in M holes and M < N, then at least two pigeons roost in the same hole.

Memoization

External Definition


Wikibooks

Up to date as of January 23, 2010

From Wikibooks, the open-content textbooks collection

The text in its current form is incomplete.

logo This preliminary outline is at present incomplete
Your suggestions in improving it are welcome. Please either edit this page to include your suggestions or leave them at the book's discussion page.

Preliminaries

The Pigeonhole Principle

Pairing problem

  • General principles
  • P. Hall's selection theorem
  • Applications to Latin squares and to coverings by dominoes of pruned chessboards.

The inclusion-exclusion principal

  • Applications to derangements
  • Applications to counting problems
  • Applications to rook polynomialss

Linear recurrence relations

Generating functions

Catalan numbers

Partitions

  • Counting various types of partitions
  • Ferrers graphs
  • Self-conjugate partitions

Symmetric functions (and anti-symmetric functions)

  • Monomial symmetric functions
  • Elementary symmetric functions
  • Theory of equations
  • Newton's formulae and relations between symmetric functions
  • Indexing of symmetric functions by partitions.

Sequences and Partial Orders

Ramsey Theory

External links

  1. Lectures on Advances in Combinatorics
  2. Applied Combinatorics

Simple English

Combinatorics is a branch of mathematics. It is concerned with the following problems:

  • Determining how many different ways there are to arrange a number of objects.
  • How many ways are there to select a number of objects from a bigger set

The objects to be arranged or selected from can be uniform, or different. Sometimes it is possible to tell them apart.

Examples

[[File:|thumb|right|All the possibilities to arrange three differently colored balls]]

  • There are 6 different ways to arrange three distinguishable objects (as shown in the graphics)
  • There are three different ways to select one particular orange from a basket with three oranges
  • There is only one possible way to select the apple from a basket that has one orange, one apple and one pear in it.


Advertisements






Got something to say? Make a comment.
Your name
Your email address
Message