Combinatorics is the study of the ways of choosing and arranging objects from given collections and the study of other kinds of problems to do with counting the number of ways to do something.
Miscellaneous topics in combinatorics
Bell numberThe number of ways that n distinguishable objects (such as differently colored balls) can be grouped into sets (such as buckets) if no set can be empty. For example, if there are three balls, colored red (R), green (G), and blue (B), they can be grouped in five different ways: (RGB), (RG)(B), (RB)(G), (BG)(R), and (R)(G)(B), so that the third Bell number is 5. The sequence of Bell numbers, 1, 2, 5, 15, 52, 203, 877, 4140, 21147,..., can be built up in the form of a triangle, as follows. The first row has just the number one. Each successive row begins with the last number of the previous row and continues by adding the number just written down to the number immediately above and to the right of it.
2 3 5
5 7 10 15
15 20 27 37 52
The Bell numbers appear down the left-hand side of the triangle. These normal Bell numbers contrast with ordered Bell numbers, which count the number of ways of placing n distinguishable object (balls) into one or more distinguishable sets (buckets) The ordered Bell numbers are 1, 3, 13, 75, 541, 4683, 47293, 545835, ...
Bell numbers, named after Eric Temple Bell, who was one of the first to analyze them in depth, are related to the Catalan numbers.
binomialA polynomial expression containing two terms, joined by + or -. The binomial theorem (see below) gives the result of raising a binomial expression to a power; the expansion and the series it leads to are called the binomial expansion and the binomial series. A binomial distribution is described by a formula related to the binomial expansion. A binomial equation is a particular kind of equation that contains two terms.
binomial coefficientAny of the coefficients of the powers of x or y in the expansion (see binomial theorem, below) of (x + y)n.
The binomial coefficient of a typical term x(n - m)ym, written nCm, or (mn), gives the number of ways of picking m unordered outcomes from n possibilities, and is also known as a combination. It has the value n!/(n - m)!m!
The binomial coefficients form the rows of Pascal's triangle.
binomial theoremA method of expanding the binomial (see above) expression (x + y)n into a finite or infinite series of powers of x and y, where n is a number either integral or fractional, positive or negative, rational or irrational; thus
The coefficients ai are called binomial coefficients.
The binomial theorem was discovered by Isaac Newton about 1666, and was first published in 1704 in the second appendix to Newton's Optics. That particular case of the theorem when n is a positive integer was known to mathematicians prior to Newton (e.g., Briggs and Pascal), and Newton himself gave no demonstration of the truth of his theorem.
Catalan numberAny number, un, from the Catalan sequence defined by
It begins: 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012, 742900, ... The values of un represent the number of ways a polygon with n + 2 sides can be cut into n triangles using straight lines joining vertices and are named after the Belgian mathematician Eugène Catalan (1814-1894). They also arise in other counting problems, for example in determining how many ways 2n beans can be divided into two containers if one container can never have less than the second.
Cayley's mousetrapA permutation problem invented by Arthur Cayley. Write the numbers 1, 2, ..., n on a set of cards, and shuffle the deck. Now, start counting using the top card. If the card chosen does not equal the count, move it to the bottom of the deck and continue counting forward. If the card chosen does equal the count, discard the chosen card and begin counting again at 1. The game is won if all cards are discarded, and lost if the count reaches n + 1. The number of ways the cards can be arranged such that at least one card is in the proper place for n = 1, 2, ..., are 1, 1, 4, 15, 76, 455, ...
Experienced ringers test and extend their abilities by ringing peals: 5,000 or more changes without breaks or repeating a row. Peals customarily last about three hours. The first peal was rung in England in 1715. Chiming bells (swinging them through a short arc using a rope and a lever) goes well back into the Middle Ages, but it wasn't until the 17th century that ringers developed the full wheel, which allowed enough control for orderly ringing. In 1668 Fabian Stedman published Tintinnalogia (The Art of Change Ringing), containing all the available information on systematic ringing. The theory of change ringing set forth by Stedman has been refined in later years but remains essentially unchanged today. Bells for change ringing are hung in stout frames that allow the bells to swing through 360°. Each bell is attached to a wooden wheel with a handmade rope running around it and takes about 2 seconds to rotate. The bells are arranged in the frame so their ropes hang in a circle in the ringing chamber below. Into each rope is woven a tuft of brightly colored wool (a sally), which marks where the ringer must catch the rope while ringing. Bells are rung from the "mouth up" position. With a pull of the rope, the bell swings through a full circle to the up position again. With the next pull it swings back in the other direction. The plot of Dorothy Sayers' The Nine Tailors (1934), considered one of her best works, revolves around the art of change ringing.
combinationA set of objects selected without reference to the order in which they are arranged. Compare with permutation (below).
combinatorial analysisThe branch of mathematics dealing with subdivisions of sets; its primary concerns are combinations and permutations and partitions. A partition of a number n is its expression in the form of a sum of positive integers: i.e., setting
n = a1 + a2 + ... + an.For example, the number 5 has 7 partitions: (1 + 1 + 1 + 1 + 1), (2 + 1 + 1 + 1), (2 + 2 + 1), (3 + 1 + 1), (3 + 2), (4 + 1), and (5).
By extension combinatorial topology is the study of complex forms in terms of their being built up from combinations of basic geometric forms.
partition numberA number that gives the number of ways of placing n indistinguishable balls into n indistinguishable urns. For example:
1: (*)The sequence runs: 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, ... If the urns are distinguishable, the number of ways is 2n. If the balls are distinguishable, the number of ways is given by the nth Bell number.
The numbers in Pascal's triangle give the number of ways of picking r unordered outcomes from n possibilities. This is equivalent to saying that the numbers in each row are the binomial coefficients in the expansion of (x + y)n:
(x + y)0 = 1
(x + y)1 = 1x + 1y
(x + y)2 = 1x2 + 2xy + 1y2
(x + y)3 = 1x3 + 3x2y + 3xy2 + 1y3
(x + y)4 = 1x4 + 4x3y + 6x2y2 + 4xy3 + 1y4
and so on. In addition, the shallow diagonals of the triangle sum to give the numbers in the Fibonacci sequence.
Pascal's triangle also has the following properties:
partitionA particular ordering of a collection of objects. For example, if an athlete has won three medals, a bronze one (B), a silver one (S), and a gold one (G), there are six ways they can be permuted or lined up: BSG, BGS, SBG, SGB, GBS, and GSB. If six people want to sit on the same park bench, there are 720 ways in which they can organize themselves. In general, n things can be permuted in n × (n - 1) × (n - 2) × ... × 2 × 1 = n! ways (where "!" is the symbol for factorial). How about if there are n distinct objects but we want to permute them in groups of k (where k n). How many ways can that be done? The first member of the group can be picked in n ways because there are n objects to pick from. The second member can be filled in (n - 1) ways since one of the n elements has already been taken. The third member can be filled in (n - 2) ways since 2 elements have already been used, and so. This pattern continues until there are k things have been chosen. This means that the last member can be filled in (n - k + 1) ways. Therefore a total of n (n - 1)(n - 2) ... (n - k + 1) different permutations of k objects, taken from a pool of n objects, exist. If we denote this number by P(n, k), we can write P(n, k) = n! / (n - k)!
Ramsey theoryA branch of mathematics that asks questions such as: Can order always be found in what appears to be disorder? If so, how much can be found and how big a chunk of disorder is needed to find a particular amount of order in it? Ramsey theory is named after the English mathematician Frank P. Ramsey (1904–1926) who started the field in 1928 while wrestling with a problem in logic. (Frank's one-year-younger brother, Arthur, served as Archbishop of Canterbury from 1961 to 1974.) His life was cut short in 1930, at the age of 26, following a bout of jaundice. Ramsey suspected that if a system was big enough, even if it seemed to be disorderly to an arbitrary degree, it was bound to contain pockets of order from which information about the system could be gleaned.
schoolgirls' problemA problem in combinatorics posed by the Thomas Kirkman in 1847:1
A school mistress has fifteen girl pupils and she wishes to take them on a daily walk. The girls are to walk in five rows of three girls each. It is required that no two girls should walk in the same row more than once per week. Can this be done?In fact, provided n is divisible by 3, we can ask the more general question about n schoolgirls walking for (n - 1)/2 days so that no girl walks with any other girl in the same triplet more than once. Solutions for n = 9, 15, and 27 were given in 1850 and much work was done on the problem thereafter. It is important in the modern theory of combinatorics.
thirty-six officers problemArrange 36 officers in a 6 × 6 square so that one officer from each of six regiments appears in each row and one from each of six ranks appears in each column. This problem, first posed by Leonhard Euler in 1779, is equivalent to finding two mutually orthogonal Latin squares of order six. Euler correctly conjectured that there was no solution; the search for a proof led to important developments in combinatorics.
Related supercategory MATHEMATICS
Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact