COMBINATORICS

also called Combinatorial Mathematics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Examples of combinatorial problems are: (1) What fraction of the possible 5-card hands dealt from a standard 52-card deck have a pair of aces? (2) How can the classes at a school be scheduled so as to accommodate the course selections of all students? (3) How many rods one inch in diameter will fit inside a hollow cylinder two feet in diameter? (4) For a given section of some city, is it possible to devise a postman's tour that traverses each block in that section once without repeating any block (starting and ending at the post office)? (5) In a group of six people, is it always true that three of the people are mutually acquainted (each pair of these three had previously met) or else that some three are mutual strangers? The problem of class scheduling is so complex that without a high-speed digital computer it could not be solved within the school year. Combinatorial mathematics has little systematic problem-solving framework. Combinatorial problems cannot be formulated in terms of continuous functions, and there are no standard algebraic manipulations or plots to help solve such problems. Combinatorics has a diverse complexity requiring a careful logical analysis that is often different for each new problem. Combinatorics has its roots in antiquity but has grown in importance in recent years because of its uses in computer and management sciences. Combinatorial problems also arise in other fields of mathematics, such as number theory and algebra. Basic combinatorics took form in the 17th and early 18th centuries. The leading contributors to the field were the Bernoulli brothers, Pierre de Fermat, Galileo Galilei, G.W. Leibniz, and Blaise Pascal. The motivation for much of early combinatorics was the analysis of gambling games and involved questions similar to the example about the chances of getting a pair of aces in a five-card poker hand. The first major combinatorial computations, made by Galileo, determined the relative likelihoods of different sums when rolling two or more dice. Such analysis of gambling odds was also the start of probability theory. In the 18th and 19th centuries, probability theory and statistics came to draw more on continuous than on combinatorial mathematics, but the advent of computers has made combinatorial approaches to statistical testing feasible and widely used. The essence of combinatorial reasoning is a logical and exhaustive analysis of possibilities in a given situation, breaking a problem into various steps and subcases. The analysis of an immense number of possible solutions to a problem is greatly simplified if the underlying structure can be found and used to narrow the possibilities. Problems involving maps and networks constitute a major subfield of combinatorics called graph theory. also called combinatorial mathematics, the field of mathematics concerned with problems of selection, arrangement, and operation within a finite or discrete system. Included is the closely related area of combinatorial geometry. One of the basic problems of combinatorics is to determine the number of possible configurations (e.g., graphs, designs, arrays) of a given type. Even when the rules specifying the configuration are relatively simple, enumeration may sometimes present formidable difficulties. The mathematician may have to be content with finding an approximate answer or at least a good lower and upper bound. In mathematics, generally, an entity is said to exist if a mathematical example satisfies the abstract properties that define the entity. In this sense it may not be apparent that even a single configuration with certain specified properties exists. This situation gives rise to problems of existence and construction. There is again an important class of theorems that guarantee the existence of certain choices under appropriate hypotheses. Besides their intrinsic interest, these theorems may be used as existence theorems in various combinatorial problems. Finally, there are problems of optimization. As an example, a function f, the economic function, assigns the numerical value f(x) to any configuration x with certain specified properties. In this case the problem is to choose a configuration x0 that minimizes f(x) or makes it e = minimalthat is, for any number e > 0, f(x0) f(x) + e, for all configurations x, with the specified properties. Additional reading James Legge (trans.), The Y-King, vol. 16 of the Sacred Books of the East (1882, reprinted 1962); Algebra, with Arithmetic and Mensuration from the Sanscrit of Brahmagupta and Bhskara, trans. by H.T. Colebrooke (1817); and Nasir ad-Din al-Tusi, Handbook of Arithmetic Using Board and Dust, Math. Rev., 31:5776 (1966), complete Russian trans. by S.A. Ahmedov and B.A. Rozenfeld in Istor.-Mat. Issled., 15:431444 (1963), give glimpses of some of the early beginnings of the subject in the Orient. The term combinatorial was first used in Gottfried Wilhelm Leibniz, Dissertatio de arte combinatoria (1666). W.W. Rouse Ball, Mathematical Recreations and Essays, rev. by H.S. MacDonald Coxeter (1942), contains an account of some of the famous recreational combinatorial problems of the 19th century, such as the problem of eight queens, Hamiltonian circuits, and the Kirkman schoolgirl problem. Eugen Netto, Lehrbuch der Combinatorik, 2nd ed. (1927, reprinted 1958); and Percy A. MacMahon, Combinatory Analysis, 2 vol. (191516, reprinted 1960), show the state of the subject in the early part of the 20th century. Herbert J. Ryser, Combinatorial Mathematics (1963); Marshall Hall, Jr., Combinatorial Theory (1967); C.L. Liu, Introduction to Combinatorial Mathematics (1968), all deal with combinatorics in general. John Riordan, An Introduction to Combinatorial Analysis (1958); and Claude Berge, Principes de combinatoire (1968; Eng. trans., Principles of Combinatorics, 1971), deal with problems of enumeration. Claude Berge, Thorie des graphes et ses applications (1957; Eng. trans., The Theory of Graphs and Its Applications, 1962); Claude Berge and A. Ghouilahouri, Programmes, jeux et rseaux de transport (1962; Eng. trans., Programming, Games and Transportation Networks, 1965); Frank Harary, Graph Theory (1969), deal with graph theoretic problems. Oystein Ore, The Four-Color Problem (1967), gives an introduction to this problem. Peter Dembowski, Finite Geometries (1968), contains most of the important developments on designs, including partially balanced and group divisible designs. Elwyn R. Berlekamp, Algebraic Coding Theory (1968), may be consulted for combinatorial aspects of coding theory. Marshall Hall, Jr., A Survey of Combinatorial Analysis, in Surveys in Applied Mathematics, vol. 4 (1958), gives a very good survey of combinatorial developments up to 1958. E.F. Beckenbach (ed.), Applied Combinatorial Mathematics (1964), gives a good idea of the wide range of applications of modern combinatorics. G.C. Rota, Combinatorial Analysis, in G.A.W. Boehm (ed.), The Mathematical Sciences: A Collection of Essays (1969), in addition to surveying some of the famous combinatorial problems brings out modern trends and indicates where combinatorics is headed. Hugo Hadwiger and Hans Debrunner, Combinatorial Geometry in the Plane (1964); I.M. Yaglom and V.G. Boltyansky, Convex Figures (1961; orig. pub. in Russia, 1951); V.G. Boltyansky, Equivalent and Equidecomposable Figures (1963; orig. pub. in Russian, 1956); and L.A. Lyusternik, Convex Figures and Polyhedra (1966; orig. pub. in Russian, 1956), deal with aspects of combinatorial geometry on an elementary level. On an advanced level, see H.S. MacDonald Coxeter, Regular Polytopes, 2nd ed. (1963); L. Fejes Toth, Lagerungen in der Ebene, auf der Kugel und im Raum (1953) and Regular Figures (1964); Branko Grunbaum, Convex Polytopes (1967) and Arrangements and Spreads (1972); and C.A. Rogers, Packing and Covering (1964). See also Kenneth P. Bogart, Introductory Combinatorics (1983); and R.J. Wilson (ed.), Applications of Combinatorics (1982), both accessible to laymen. Raj C. Bose Branko Grnbaum Combinatorial geometry The name combinatorial geometry, first used by Hadwiger, is not quite accurately descriptive of the nature of the subject. Combinatorial geometry does touch on those aspects of geometry that deal with arrangements, combinations, and enumerations of geometric objects; but it takes in much more. The field is so new that there has scarcely been time for it to acquire a well-defined position in the mathematical world. Rather it tends to overlap parts of topology (especially algebraic topology), number theory, analysis, and, of course, geometry. The subject concerns itself with relations among members of finite systems of geometric figures subject to various conditions and restrictions. More specifically, it includes problems of covering, packing, symmetry, extrema (maxima and minima), continuity, tangency, equalities, and inequalities, many of these with special emphasis on their application to the theory of convex bodies. A few of the fundamental problems of combinatorial geometry originated with Newton and Euler; the majority of the significant advances in the field, however, have been made since 1946. The unifying aspect of these disparate topics is the quality or style or spirit of the questions and the methods of attacking these questions. Among those branches of mathematics that interest serious working mathematicians, combinatorial geometry is one of the few branches that can be presented on an intuitive basis, without recourse by the investigator to any advanced theoretical considerations or abstractions. Yet the problems are far from trivial, and many remain unsolved. They can be handled only with the aid of the most careful and often delicate reasoning that displays the variety and vitality of geometric methods in a modern setting. A few of the answers are natural and are intuitively suggested by the questions. Many of the others, however, require proofs of unusual ingenuity and depth even in the two-dimensional case. Sometimes a plane solution may be readily extendible to higher dimensions, but sometimes just the opposite is true, and a three-dimensional or n-dimensional problem may be entirely different from its two-dimensional counterpart. Each new problem must be attacked individually. Attempts to create standard methods or theories capable of being applied to the solution of any significant group of the currently unsolved problems in the field had by the late 20th century met with no success. The continuing charm and challenge of the subject are at least in part due to the relative simplicity of the statements coupled with the elusive nature of their solutions. Some historically important topics of combinatorial geometry Packing and covering Figure 7: Packing of disks. It is easily seen that six equal circular disks may be placed around another disk of the same size so that the central one is touched by all the others but no two overlap (Figure 7) and that it is not possible to place seven disks in such a way. In the analogous three-dimensional situation, around a given ball (solid sphere) it is possible to place 12 balls of equal size, all touching the first one but not overlapping it or each other. One such arrangement may be obtained by placing the 12 surrounding balls at the midpoints of edges of a suitable cube that encloses the central ball; each of the 12 balls then touches four other balls in addition to the central one. But if the 12 balls are centred at the 12 vertices of a suitable regular icosahedron surrounding the given ball, there is an appreciable amount of free space between each of the surrounding balls and its neighbours. (If the spheres have radius 1, the distances between the centres of the surrounding spheres are at least 2/cos 18 = 2.1029 .) It appears, therefore, that by judicious positioning it might be possible to have 13 equal non-overlapping spheres touch another of the same size. This dilemma between 12 and 13, one of the first nontrivial problems of combinatorial geometry, was the object of discussion between Isaac Newton and David Gregory in 1694. Newton believed 12 to be the correct number, but this claim was not proved until 1874. The analogous problem in four-dimensional space is still open, the answer being one of the numbers 24, 25, or 26. The problem of the 13 balls is a typical example of the branch of combinatorial geometry that deals with packings and coverings. In packing problems the aim is to place figures of a given shape or size without overlap as economically as possibly, either inside another given figure or subject to some other restriction. Figure 8: Covering of part of a plane with triangles. Problems of packing and covering have been the objects of much study, and some striking conclusions have been obtained. For each plane convex set K, for example, it is possible to arrange nonoverlapping translates of K so as to cover at least two-thirds of the plane; if K is a triangle (and only in that case), no arrangement of nonoverlapping translates covers more than two-thirds of the plane (Figure 8). On the other hand, many easily stated questions are still open. One of them concerns the densest packing of spheres. If the spheres are packed in cannonball fashionthat is, in the way cannonballs are stacked to form a triangular pyramid, indefinitely extendedthen they fill p/, or about 0.74, of the space. Whether this is the greatest density possible is not known, but it was proved in 1958 by the British mathematician C. Ambrose Rogers that, if there exists a closer packing, its density cannot exceed 0.78. Covering problems deal in an analogous manner with economical ways of placing given figures so as to cover (that is, contain in their union) another given figure. One famous covering problem, posed by the French mathematician Henri Lebesgue in 1914, is still unsolved: What is the size and shape of the universal cover of least area? Here a convex set C is called universal cover if for each set A in the plane such that diam A 1 it is possible to move C to a suitable position in which it covers A. The diameter diam A of a set A is defined as the least upper bound of the mutual distances of points of the set A. If A is a compact set, then diam A is simply the greatest distance between any two points of A. Thus, if A is an equilateral triangle of side 1, then diam A = 1; and if B is a cube of edge length 1, then diam B = . Design theory BIB (balanced incomplete block) designs. A design is a set of T = {1, 2, . . . , u} objects called treatments and a family of subsets B1, B2, . . . , Bb of T, called blocks, such that the block Bi contains exactly ki treatments, all distinct. The number ki is called the size of the block Bi, and the ith treatment is said to be replicated ri times if it occurs in exactly ri blocks. Specific designs are subject to further constraints. The name design comes from statistical theory in which designs are used to estimate effects of treatments applied to experimental units. A BIB design is a design with u treatments and b blocks in which each block is of size k, each treatment is replicated r times, and every pair of distinct treatments occurs together in l blocks. The design is said to have the parameters (u, b, r, k, l). Some basic relations are easy to establish (see 20). These conditions are necessary but not sufficient for the existence of the design. The design is said to be proper if k 2. A PBIB design is obtained by identifying the u treatments with the u objects of an association scheme and arranging them into b blocks satisfying the following conditions: A. Each contains k treatments. B. Each treatment occurs in r blocks. C. If two treatments are ith associates, they occur together in li blocks. Two-class association schemes and the corresponding designs are especially important both from the mathematical point of view and because of statistical applications. For a two-class association scheme the constancy of u, ni, p111, and p112 ensures the constancy of the other parameters. Seven relations hold (see 23). Sufficient conditions for the existence of association schemes with given parameters are not known, but for a two-class association scheme Connor and the U.S. mathematician Willard H. Clatworthy in 1954 obtained some necessary conditions (see 24). Graph theory Definitions A graph G consists of a non-empty set of elements V(G) and a subset E(G) of the set of unordered pairs of distinct elements of V(G). The elements of V(G), called vertices of G, may be represented by points. If (x, y) E(G), then the edge (x, y) may be represented by an arc joining x and y. Then x and y are said to be adjacent, and the edge (x, y) is incident with x and y. If (x, y) is not an edge, then the vertices x and y are said to be nonadjacent. G is a finite graph if V(G) is finite. A graph H is a subgraph of G if V(H) V(G) and E(H) E(G). A chain of a graph G is an alternating sequence of vertices and edges x0, e1, x1, e2, en, xn, beginning and ending with vertices in which each edge is incident with the two vertices immediately preceding and following it. This chain joins x0 and xn and may also be denoted by x0, x1, , xn, the edges being evident by context. The chain is closed if x0 = xn and open otherwise. If the chain is closed, it is called a cycle, provided its vertices (other than x0 and xn) are distinct and n 3. The length of a chain is the number of edges in it. Figure 3: Two isomorphic graphs and a tree. A graph G is labelled when the various u vertices are distinguished by such names as x1, x2, xu. Two graphs G and H are said to be isomorphic (written G H) if there exists a oneone correspondence between their vertex sets that preserves adjacency. For example, G1 and G2, shown in Figure 3, are isomorphic under the correspondence xi yi. Figure 3: Two isomorphic graphs and a tree. Two isomorphic graphs count as the same (unlabelled) graph. A graph is said to be a tree if it contains no cyclefor example, the graph G3 of Figure 3. Enumeration of graphs The number of labelled graphs with u vertices is 2u(u - 1)/2 because u(u - 1)/2 is the number of pairs of vertices, and each pair is either an edge or not an edge. Cayley in 1889 showed that the number of labelled trees with u vertices is uu - 2. The number of unlabelled graphs with u vertices can be obtained by using Polya's theorem. The first few terms of the generating function F(x), in which the coefficient of xu gives the number of (unlabelled) graphs with u vertices, can be given (see 27). A rooted tree has one point, its root, distinguished from others. If Tu is the number of rooted trees with u vertices, the generating function for Tu can also be given (see 28). Polya in 1937 showed in his memoir already referred to that the generating function for rooted trees satisfies a functional equation (see 29). Letting tu be the number of (unlabelled) trees with u vertices, the generating function t(x) for tu can be obtained in terms of T(x) (see 30). This result was obtained in 1948 by the American mathematician Richard R. Otter. Many enumeration problems on graphs with specified properties can be solved by the application of Polya's theorem and a generalization of it made by a Dutch mathematician, N.G. de Bruijn, in 1959. Problems of enumeration Permutations and combinations Binomial coefficients An ordered set a1, a2, . . . , ar of r distinct objects selected from a se55t of n objects is called a permutation of n things taken r at a time. The number of permutations is given by nPn = n(n - 1)(n - 2) (n - r + 1). When r = n, the number nPr = n(n - 1)(n - 2) is simply the number of ways of arranging n distinct things in a row. This expression is called factorial n and is denoted by n!. It follows that nPr = n!/(n - r)!. By convention 0! = 1. A set of r objects selected from a set of n objects without regard to order is called a combination of n things taken r at a time. Because each combination gives rise to r! permutations, the number of combinations, which is written (n/r), can be expressed in terms of factorials (see formula 1). The number (n/r) is called a binomial coefficient because it occurs as the coefficient of prqn - r in the binomial expansionthat is, the re-expression of (q + p)n in a linear combination of products of p and q (see 2). in the binomial expansion is the probability that an event the chance of occurrence of which is p occurs exactly r times in n independent trials (see probability theory). The answer to many different kinds of enumeration problems can be expressed in terms of binomial coefficients. The number of distinct solutions of the equation x1 + x2 + + xn = m, for example, in which m is a non-negative integer m n and in which only non-negative integral values of xi are allowed is expressible this way, as was found by the 17th18th-century French-born British mathematician Abraham De Moivre (see 3). Multinomial coefficients If S is a set of n objects, and n1, n2, , nk are non-negative integers satisfying n1 + n2 + + nk = n, then the number of ways in which the objects can be distributed into k boxes, X1, X2, , Xk, such that the box Xi contains exactly ni objects is given in terms of a ratio constructed of factorials (see 4). This number, called a multinomial coefficient, is the coefficient in the multinomial expansion of the nth power of the sum of the {pi} (see 5). If all of the {pi} are non-negative and sum to 1 and if there are k possible outcomes in a trial in which the chance of the ith outcome is pi, then the ith summand in the multinomial expansion is the probability that in n independent trials the ith outcome will occur exactly ni times, for each i, 1 i k.