Permutations and combinations

Summary: For centuries, mathematicians have posed and studied problems that involve various arrangements or groupings of sets of objects, which are known as permutations and combinations.

In a very broad sense, combinatorics is about counting. The mathematical discipline of combinatorics addresses the enumeration, permutation, and combination of sets of objects, as well as their relations and properties. Combinatorial problems can be found in many areas of pure and applied mathematics, including algebra, topology, geometry, probability, graph theory, optimization, computer science, and statistical physics. One of the earliest problems in combinatorics is found in the work of Greek biographer Plutarch, who described mathematician Xenocrates of Chalcedon’s work on calculating how many syllables could be produced by taking combinations of the letters of the alphabet. This occurred between 400 and 300 b.c.e. Millennia later, mathematician William Gowers won the 1998 Fields Medal, widely regarded as the most prestigious prize in mathematics, for his “contributions to functional analysis, making extensive use of methods from combination theory.” In twenty-first-century school curricula, primary school children study number combinations to facilitate learning basic operations like addition, subtraction, multiplication, and division. High school students often study permutations and combinations as counting techniques. Permutations and combinations were fundamental for cracking the World War II Enigma code and continue to remain vital in cryptography, among other fields.

Definitions

In mathematical fields like algebraic group theory, combinatorics, or probability, the term “permutation” has several meanings that are all essentially related to the idea of rearranging, ordering, or permuting some kind of mathematical object. When paired with combinations, particularly in primary and secondary curricula, a permutation is usually thought of as an ordered arrangement of some set or subset of objects. For example, for the set of objects a, b, and C, there are six permutations of the set: {A, B, C}, {A, C, B}, {B, A, C}, {B, C, A}, {C, A, B}, and {C, B, A}. A combination is then a subset of objects selected from a larger set, where order does not matter. For example, for the set a, b, and C, one combination of two objects is {A, B}. In some applications, the objects in a combination are thought of as being chosen sequentially. However, since order does not matter, the selection {B, A} would represent the same combination as {A, B}. All possible two-object combinations are {A, B}, {B, C}, {A, C}. Mathematicians Blaise Pascal and Gottfried Leibniz used the specific term “combinations” beginning in the seventeenth century, while Jacob Bernoulli is often credited with introducing the term “permutations” a short while later. Some alternatively trace it to Thomas Strode in the seventeenth century.

History and Early Applications

The real-world motivation for many early problems involving what are now called “combinations” and “permutations” was religion. For example, Jaina, Christian, and Jewish scholars were interested in letter permutations, which some believed had spiritual power. In the ninth century, the Jaina mathematician Mahavira discussed rules for using permutations and combinations. In the tenth century, Rabbi Abraham ben Meir ibn Ezra used combinations to study the conjunction of planets. Another motivator was games of chance, which also drove probability theory. Archaeological evidence suggests that gambling has been around since the dawn of humankind, and many games rely on players achieving special combinations of symbols or objects like knucklebones, sticks, or polyhedral dice. Surviving writings show that Egyptian, Greek, Hindu, Islamic, and perhaps Chinese scholars and mathematicians studied permutations and combinations.

The Egyptian game “Hounds and Jackals” used a set of “throw” sticks that resulted in combinations of outcomes that determined how far a player might move. In the sixth century b.c.e., Hindus discussed combinations of six tastes: sweet, acid, saline, pungent, bitter, and astringent. Some consider the Chinese divination text I-Ching to be part of the literature on combinations and permutations since it discussed arrangements sets of trigram and hexagram symbols. Versions date to at least 400–300 b.c.e. In the sixth century, Roman philosopher Anicius Manlius Severinus Boëthius presented a rule for finding the possible combinations of objects taken two at a time from some set.

In the tenth and eleventh centuries, mathematicians like Acharya Hemachandra explored the how many combinations of short and long syllables were possible in a line of text with a fixed length, and Bhaskara’s treatise Bhaskaracharyai contained an entire chapter devoted to combinations, among other chapters on topics like arithmetic, geometry, and progressions. Both al-Marrakushi ibn Al-Banna and Kamal al-Din Abu’l Hasan Muhammad Al-Farisi explored the relationship between polygonal numbers, the binomial theorem, and combinations. Al-Farisi used what historians consider a form of induction to show the relationship between triangular numbers (numbers that can be represented by an equilateral triangular grid of points such as, 1, 3, 6, 10), and the combinations of subsets of objects drawn from a larger set. Mi’yar al-’aqul ibn Sina (Avicenna) developed a system of combinations of “simple” machines to classify complex mechanisms.

The original concept of simple machines is attributed to mathematician Archimedes of Syracuse. A group might be machines containing rollers and levers, chosen from a larger set of possibilities that included windlasses, pulleys, rollers, levers, and other components. Starting in the Renaissance, the most commonly recognized set of six simple machines was the lever, inclined plane, wheel and axle, screw, wedge, and pulley. Students continue to discuss more complex machines as combinations of simple machines.

In Europe, beginning around the twelfth century and up through the nineteenth century, many mathematicians such as Levi ben Gerson, Bernoulli, Leibniz, Pascal, Pierre Fermat, Abraham de Moivre, George Boole, and John Venn worked on the development of combinations and permutations, frequently in the context of probability theory. For example, Johann Buteo (or Jean Borell) discussed the possible throws of four dice as well as locks with movable combination cylinders in his sixteenth-century work Logistica.

Bernoulli’s Ars Conjectandi collected knowledge of permutations and combinations through the seventeenth century and was a popular combinatorics book in the eighteenth century. However, standard notation for permutations and combinations was still emerging.

Factorials

A mathematical function called a factorial is used to compute the number of possible permutations and combinations. Let n! equal

n × (n − 1)×(n − 2)×(n − 3)×…×3×2×1.

For example, 5!=5×4×3×2×1=120. Further, 0! is defined to be 1. Bernoulli had proved many factorial results, like the fact that n! gives the number of permutations of n objects. The use of the exclamation point to indicate a factorial, which was more convenient for printers of the day than some older notations, has been attributed to mathematician Christian Kramp. He worked in the late eighteenth and early nineteenth centuries. The general rule for finding permutations and combinations is sometimes attributed to Bernoulli and sometimes to sixteenth and seventeenth century mathematician Pierre Hérigone, who is also famed for introducing a variety of mathematical and logical notations. However, mathematicians used their own methods for indicating permutations and combinations well into the nineteenth century. For example, Thomas Harriot’s seventeenth-century work Ars Analyticae Praxis contained unique symbolism for displaying the combinatorial process of finding binomial products.

In the notation common in the twentieth and twenty-first centuries, the number of permutations is stated as nPr where n is the total number of objects in a set and r is the number of objects selected from n and permuted,

The number of combinations is nCr, which is read as “n choose r,”

The partial origins of this approach may perhaps be traced to nineteenth-century amateur mathematician Jean Argand, who used (m, n) to represent combinations of n objects chosen from a set of m objects.

Modern Developments

In the early twentieth century, mathematicians and others continued to develop theories and applications of combinatorial concepts. For example, statistician Ronald Fisher applied combinations to the design of factorial experiments, while artist Maurits Cornelius (M.C.) Escher developed his own system for categorizing combinations of shape, color, and symmetrical properties, which can be found in his 1941 notebook later referred to as a paper, Regular Division of the Plane with Asymmetric Congruent Polygons. Historians discuss that the sketchbooks of a typical artist contain preliminary versions of final works. Escher’s book, on the other hand, appeared to form a theoretical mathematical basis for his tiling work. These combinatorial categories also influenced the field of crystallography.

Circular permutations are also common. One could think of lining up six people in a straight line to take their picture versus seating them at a round table. There are n! permutations of the people lined up. However, once all six people are seated, even if they were all asked to move over one seat, they would all still be seated in the same overall order. There are therefore (n-1)! ways of putting objects in a circle. Another possibility is that all items in the set are not unique, like the letters in “Mississippi,” which reduces the number of unique permutations and combinations versus a set of the same length with unique components.

Permutation Groups

In a field like modern algebra, permutations can be viewed as maps that relate a set to itself. The set of permutations is then collected into an algebraic structure called a “group.” One example is the various possible transformations of a Rubik’s Cube puzzle, named for Erno Rubik. There are 43,252,003,274,489,856,000 permutations in the group for a 3-by-3-by-3 Rubik’s Cube. Mathematicians often use software like the Groups, Algorithms, Programming (GAP) system to model and understand the transformations. Theories about permutation groups have been traced by historians to at least as far back as Joseph Lagrange’s 1770 work Réflexions sur la résolution algébrique des équations, in which he discussed the permutations of the roots of equations and considered those roots as abstract structures. Paolo Ruffini used what would now be called group theory in his work, including permutation groups, and proved many fundamental theorems. In the nineteenth century, Augustin-Louis Cauchy generalized some of Ruffini’s results. He studied permutation groups and proved what is now known as Cauchy’s theorem. High school mathematics teacher Peter Sylow wrote his book Théorèmes sur les groupes de substitutions in the latter half of the nineteenth century, and it contained what are now known as the three Sylow theorems, which he proved for permutation groups. Arthur Cayley wrote about the connections between his work on permutations and Cauchy’s, extended the notion of permutation groups into the broader idea of algebraic groups, and ultimately proposed that matrices and quaternions were types of groups. Some of his work served as one foundation for physicist Werner Heisenberg’s development of quantum mechanics.

In the early twentieth century, George Pólya used permutation groups and other methods to enumerate isomers (compounds that have the same molecular components but different structural arrangements, or permutations) in organic chemistry. He also influenced Escher’s studies of combinations. The George Pólya Prize is given every two years by the Society for Industrial and Applied Mathematics. One criterion for winning is “a notable application of combinatorial theory.” Mathematicians continue to explore permutations and combination concepts in algebra and many other areas of mathematics.

Bibliography

David, F. N. Games, Gods & Gambling: A History of Probability and Statistical Ideas. New York: Dover Publications, 1998.

Davis, Tom. “Permutation Groups.” http://www.geometer.org/mathcircles/perm.pdf.

Higgins, Peter. Number Story: From Counting to Cryptography. New York: Copernicus, 2008.