Combinatorics is a branch of 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 were 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 called a combinatorialist.

History[link]

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 6th century BCE, 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 2⁶-1 possibilities. Roman 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 numbers.^[2][3] 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. Notably, an Indian mathematician Mahavira (c. 850) provided the general formulae for the number of permutations and combinations.^{[citation needed]} 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.

In the second half of 20th century, combinatorics enjoyed a rapid growth, which led to establishment of dozens of new journals and conferences in the subject.^[6] 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.

Approaches and subfields of combinatorics[link]

Enumerative combinatorics[link]

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[link]

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[link]

A plane partition.

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[link]

Petersen graph.

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 T_G(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.^[7]

Design theory[link]

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[link]

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[link]

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[link]

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[link]

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 K_n,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[link]

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 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[link]

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[link]

Construction of a Thue-Morse infinite word.

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.

Geometric combinatorics[link]

An icosahedron.

Geometric combinatorics is related to convex and discrete geometry, in particular polyhedral combinatorics. It asks, for example, 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. We should note that combinatorial geometry is an old fashioned name for discrete geometry.

Topological combinatorics[link]

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[link]

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[link]

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

Related fields[link]

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

Combinatorial optimization[link]

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[link]

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[link]

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[link]

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[link]

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[link]

• Combinatorial biology
• Combinatorial chemistry
• Combinatorial data analysis
• Combinatorial game theory
• Combinatorial group theory
• Phylogenetics
• List of combinatorics topics

Notes[link]

References[link]

• Björner, 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.
• 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.
• 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).

External links[link]

Wikimedia Commons has media related to: Combinatorics

Look up combinatorics in Wiktionary, the free dictionary.

• 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

3-2-1 Contact is an American science educational television show that aired on PBS from 1980 to 1988, and an adjoining children's magazine. The show, a production of the Children's Television Workshop, teaches scientific principles and their applications. Dr. Edward G. Atkins, who was responsible for much of the scientific content of the show, felt that the TV program wouldn't replace a classroom but would open the viewers to ask questions about the scientific purpose of things.^[1]

History[link]

3-2-1 Contact was the brainchild of Samuel Y. Gibbon, Jr., who had been the executive producer of The Electric Company for CTW from 1971 to 1977. (Gibbon actually left CTW before Contact's production began, though he was still credited as "Senior Consultant.")

The first season of 65 programs began airing January 14, 1980 on select PBS member stations; it featured a cast of three college students who discussed science in an on-campus room known as the Workshop. The first season came to an end on April 11, 1980, but funds for more episodes were not sufficient until 1982.

When production resumed for the second season, which premiered on October 17, 1983, the show presented a more realistic appearance, as the new cast convened in a suburban basement (these segments were shot at Reeves Teletape, which also housed Sesame Street at the time). This cast continued until October 18, 1985. Ozzie Alfonso was Contact's new director and Al Hyslop its executive producer.

When the fifth season began on September 22, 1986, a third cast was introduced. However, unlike the previous casts, they did not meet in any specific setting; instead, they appeared in various taped and filmed segments. Episodes continued to be produced through November 1988.

For a time in the mid-1980s, the program was co-produced with the French television network FR3 and featured several new French cast members in addition to the American cast. From 1982 to 1983 the program was aired in Spain with dubbed-over versions of the American original broadcasts, and some local add-ons with four Spanish cast members: Sonia Martínez, Luis Bollain, Fernando Rueda and Marifé Rodríguez.^[2] Another Spanish version of the broadcast was aired from 1990 to 1992.

From September 1, 1991 until May 1, 1992, an edited version of the series titled 3-2-1 Classroom Contact was produced, specifically for in-school viewing.

It was reported in 1984 that 3-2-1 Contact had an audience of over 7 million viewers and was broadcast in 26 countries including West Germany, France, Italy and Spain making their own dubbed-over versions.^[1]

Broadcasters wanted the children to record the episodes without being afraid of infringement of copyright violations.^[1]

Hosts[link]

The Bloodhound Gang[link]

A frequent segment of the show was The Bloodhound Gang, a series about a group of young detectives who used science to solve crimes. Episodes of the series needed to be run in regular sequence for understandable viewing, as many Bloodhound Gang mysteries were cut among two or three Contact episodes.

The magazine[link]

Three months before the show premiered, a print magazine of the same name that also focused on science was released. In 1985, the magazine absorbed some of the content of sibling publication Enter (which went out of print that same year), including reader submissions of computer programs written in the BASIC computer language as well as reviews of popular computer programs. A new feature called "The Slipped Disk Show" appeared in mid-1985, starring a fictional disc jockey who answered computer-related questions submitted by readers.

Beginning in 1987, the magazine also featured content from another CTW production, Square One Television. Such content frequently took the form of a two-page comic strip, often parodying a popular show or movie of the time, with a math-related question at the end.

The Bloodhound Gang mysteries also made the leap to the magazine, but they were subsequently replaced with a series entitled The Time Team in September 1990. These stories found teenage characters Sean Nolan and Jenny Lopez traveling to different time periods in the past and future. Their surroundings and personal encounters were described with great detail, educating readers as to the customs of various cultures throughout history, and – on trips to the future – often pushing present day hot-button issues. For example, a 1993 story saw the duo traveling to what appeared to be a prehistoric forest, but near the end, they found a Brazil flag, a newspaper clipping from 1995, and a bulldozer at work: this was in fact a Brazilian rainforest being levelled.

In 1996, The Time Team was replaced by a comic serial, Cosmic Crew, which focused on the adventures of a group of teenagers and their robot butler in space. Their first story arc (which ran for more than a year) had them trying to figure out a series of riddles relating to places in the solar system in order to claim a treasure (which turned out to be a scholarship fund). Another story arc had a delinquent (who had been a villain in the first arc) join them in order to chase down a gang of other delinquents. Despite being effectively replaced, a few Time Team stories were run whenever there were gaps between installments of Cosmic Crew.

Many of the magazine's cover stories involved current events, such as 1990s oil fires in the Middle East. In addition, the magazine offered a games section in which most of the games were related to the stories in the issue.

In 1996, CTW presumably concluded that faithful readers from the late 1980s and early 1990s had long since moved on, and the magazine began to reprint non-time-sensitive stories from years past. For example, a 1991 article on the geography of the Galápagos Islands – a relatively unchanging subject – could very well re-appear in an identical format a half a decade later.

Under Sesame Workshop the magazine later became Contact Kids, removing the original reference to the television show. Production of the magazine was suspended indefinitely in 2001.

After production[link]

Though the show went off the air in 1988, it appeared in reruns from 1999 to 2003 on the cable television network Noggin, then a joint venture of CTW and Nickelodeon. Occasionally, shows were also rerun on Nickelodeon's Cable in the Classroom time period. For all these Nickelodeon and Noggin airings, the series was rated TV-Y7 (possibly due to the target audience). It also still aired on some PBS stations as reruns from 1989 to 1998 before it was switched to Noggin in 1999. As of 2003, Noggin no longer airs any shows produced by Sesame Workshop. The shows were modified for the shorter running time on these networks to allow for their interstitials.

Sources of funding[link]

Funding for 3-2-1 Contact was provided by the following:^[3]

• National Science Foundation (January 14, 1980–November 18, 1988)
• United States Department of Education (January 14, 1980–November 18, 1988)
• Corporation for Public Broadcasting (January 14, 1980–November 18, 1988)
• Andrew W. Mellon Foundation (January 14, 1980–November 18, 1988)
• IBM Corporation (January 14, 1980–November 18, 1988)
• Carnegie Corporation of New York (October 31, 1983-November 18, 1988)

Five sponsors funded the show for its entire run. They were originally supposed to fund for 20 new episodes until 1989.^[1]

References[link]

External links[link]

• 3-2-1 Contact at the Internet Movie Database
• 3-2-1 Contact at TV.com