Combinatorial analysis

combinatorial mathematics, combinatorics

The branch of mathematics devoted to the solution of problems of choosing and arranging the elements of certain (usually finite) sets in accordance with prescribed rules. Each such rule defines a method of constructing some configuration of elements of the given set, called a combinatorial configuration. One can therefore say that the aim of combinatorial analysis is the study of combinatorial configurations. This study includes questions of the existence of combinatorial configurations, algorithms and their construction, optimization of such algorithms, as well as the solution of problems of enumeration, in particular the determination of the number of configurations of a given class. The simplest examples of combinatorial configurations are permutations, combinations and arrangements.

A set of elements is called an -set; an -subset of it, , is called a combination of size . The number of combinations of size from distinct elements is equal to

The formula

is usually called the Newton binomial formula. The numbers are called binomial coefficients. An ordered -subset is called an arrangement of size . The number of arrangements of size of distinct elements is equal to

For an arrangement is a permutation of the elements of , the number of such permutations being .

The rise of the fundamental notions and developments of combinatorial analysis was parallel with the development of other branches of mathematics such as algebra, number theory, probability theory, all closely linked to combinatorial analysis. The formula expressing the number of combinations in terms of the binomial coefficients and the Newton binomial formula for positive integers was already known to the mathematicians of the Ancient Orient. Magic squares (cf. Magic square) of order three were studied for mystical ends. The birth of combinatorial analysis as a branch of mathematics is associated with the work of B. Pascal and P. (de) Fermat on the theory of games of chance. These works, which formed the foundations of probability theory, contained at the same time the principles for determining the number of combinations of elements of a finite set, and thus established the traditional connection between combinatorial analysis and probability theory.

A large contribution to the systematic development of combinatorial methods was provided by G. Leibniz in his dissertation Ars Combinatoria (the Art of Combinatorics) in which, apparently, the term "combinatorial" appeared for the first time. Of great significance for the establishment of combinatorial analysis was the paper Ars Conjectandi (the Art of Conjecturing) by J. Bernoulli; it was devoted to the basic notions of probability theory, and a number of combinatorial notions were of necessity set forth and applications to the calculation of probabilities were given. It can be said that with the appearance of the works of Leibniz and Bernoulli, combinatorial methods started to be an independent branch of mathematics.

A major contribution to the development of combinatorial methods was provided by L. Euler. In his papers on the partitioning and decomposition of positive integers into summands he laid down the beginnings of one of the basic methods of calculating combinatorial configurations, namely the method of generating functions.

The 1950s are associated with an expansion of interest in combinatorial analysis in connection with the rapid development of cybernetics and discrete mathematics and the wide application of computer techniques. In this period an interest in classical combinatorial problems was activated.

Two factors proved to be of influence in the formation of the direction of subsequent investigations. On the one hand, the choice of the objects of investigation; on the other, the formation of the aims of the investigation, depending in the final reckoning on the complexity of the objects under study. If the combinatorial configuration under investigation has a complex character, then the aim of the investigation is to elucidate the conditions for its existence and to develop algorithms for its construction.

A large well-developed branch of combinatorial analysis is the theory of block designs (cf. Block design, and also [2], [3], [10]); the main problems of this branch relate to questions of classification, conditions of existence and methods of constructing certain classes of block designs. A special case of block designs are the so-called balanced incomplete block designs or -configurations, which are defined as collections of -subsets of some -set, called blocks, with the condition that each element appears in blocks and each pair of elements in blocks. When , and hence when , a -configuration is called a -configuration, or a symmetric balanced incomplete block design. Even for -configurations the question of necessary and sufficient conditions for their existence remains unsolved (1988). For the existence of -configurations it is necessary that when is even, be a perfect square, while when is odd, the equation

must have an integral solution in , not all zero.

When , , a -configuration represents a projective plane of order and is a particular case of a finite geometry containing a finite number of points and lines under prescribed incidence conditions. Corresponding to each projective plane of order there is a unique complete set of pairwise orthogonal Latin squares of order (cf. Latin square). In order that a projective plane of order exists, it is necessary that for () there exist integers such that

An affirmative solution to the question of the existence of projective planes of order has been obtained only for , where is a prime number and is a positive integer. Even for this question remains open (1988). Related to this circle of questions is a result in connection with the falsification of the Euler conjecture on the non-existence of pairs of orthogonal Latin squares of order , (see Classical combinatorial problems).

Another direction in combinatorial analysis relates to selection theorems. At the foundation of a whole series of results along these lines is the P. Hall theorem on the existence of a system of distinct representatives (a transversal) of a family of subsets of a set , that is, a system of elements such that and when . A transversal exists if and only if for any such that , , the following inequality holds:

where is the number of elements in . A corollary of Hall's theorem is the theorem on the existence of Latin squares, stating that any Latin rectangle of order , , can be extended to a Latin square of order . Another corollary of Hall's theorem: Any non-negative matrix such that

can be represented in the form

where are permutation matrices of order and . Hall's theorem also implies that the minimum number of rows and columns of a non-negative matrix containing all positive elements is equal to the maximum number of elements that pairwise are not in the same row or in the same column. The extremal property of partially ordered sets, which is analogous to this theorem, is established by the theorem stating that the minimum number of non-intersecting chains is the same as the size of the maximal subset consisting of pairwise-incomparable elements. The following theorem also bears an extremal character: If for an -set one collects all the combinations of elements and partitions them into non-intersecting classes, then, given an integer , there exists an such that for there is a subset of elements for which all the combinations belong to the same class.

The travelling-salesman problem is an extremal problem too; it consists in composing the shortest route visiting towns and returning to the starting point, where the distances between the towns are known. This problem has applications in the study of transportation networks. Combinatorial problems of an extremal character are considered in the theory of flows in networks and in graph theory.

A significant portion of combinatorial analysis consists of enumeration problems. For their solution one either indicates a method of sorting out combinatorial configurations of a given class, or one determines the number of them, or one does both. Typical results of enumeration problems are: The number of permutations of order with cycles is equal to , where is the Stirling number of the first kind, defined by the equation

the number of partitions of a set of elements into subsets is equal to the Stirling number of the second kind

and, the number of arrangements of distinct objects in distinct cells with no cell empty is equal to .

A useful device for the solution of enumeration problems is the permanent of a matrix. The permanent of a matrix (; , ) the elements of which belong to some ring, is defined by the formula

where the summation is carried out over all possible arrangements of size from distinct elements. The number of transversals of some family of subsets of a finite set is equal to the permanent of the corresponding incidence matrix.

A whole class of problems on the determination of the number of permutations with restricted positions reduces to the calculation of permanents. For convenience, these problems are sometimes formulated as problems on the arrangement of mutually non-attacking pieces on an chessboard. Connected with the determination of the permanents of certain classes of matrices are variants of the problem of dimers, which arises in the study of the phenomenon of adsorption and consists in the determination of the number of ways of combining the atoms of di-atomic molecules on some surface. Its solution can also be obtained in terms of Pfaffians (cf. Pfaffian), which are certain functions of matrices close to determinants. The problem of the number of Latin rectangles (squares) is also connected with the development of effective methods for calculating permanents of certain -matrices.

For the calculation of permanents one applies the formula:

There are a large number of inequalities giving an estimate of the size of the permanent in certain classes of matrices. The determination of the extremal values of the permanent in specific classes of non-negative matrices is of interest. For a -matrix with given values of the number of ones in the rows one has the estimate

cf. [12]. The famous van der Waerden conjecture, that the minimum permanent of a doubly-stochastic matrix of order is equal to was proved, independently, by D.I. Falikman (1979) and G.P. Egorichev (1980), cf. [13].

An important role in the solution of enumeration problems is played by the method of generating functions (cf. Generating function). A generating function

sets up a correspondence between the sequence and the elements of some ring, and is regarded as a formal power series. According to this definition, generating functions are effectively used for the solution of enumeration problems in parallel with methods of recurrence relations and finite-difference equations. In obtaining asymptotic formulas for the generating functions, analytic functions of a real or complex variable are usually employed. In the latter case, the Cauchy integral is applied in finding expressions for the coefficients.

There are results in the direction of a possible unification of enumeration methods; these are connected with the study of so-called incidence algebras and the use of the Möbius function on a partially ordered set (see for example, [10]). In the solution of enumeration problems, an essential role is played by the formalization of the concept of indistinguishability of objects. The use of the notion of equivalence of objects with respect to a certain group of permutations in combination with the application of the method of generating functions forms the basis of the so-called Pólya theory of enumeration (see [10]), the essence of which is as follows. Consider the set of configurations

On the set , a group of permutations acts, thus defining an equivalence relation under which , , if there exists an such that for all . To each corresponds a characteristic , where , , are elements of an Abelian group. The characteristic of the configuration is given by the formula

If is the number of elements with a given value of the characteristic and is the number of inequivalent configurations ,

then Pólya's fundamental theorem states that

where is the cyclic index of the group , defined by the equation

and is the number of elements of the cyclic class (cf. Symmetric group) of . This theorem is based on Burnside's lemma: The number of equivalence classes defined on the set by the permutation group is given by the formula

where is the number of unit cycles of . Pólya's theory has applications in the solution of enumeration problems in graph theory and in the enumeration of carbon chemical compounds. There is a generalization of Pólya's theory to the case when the equivalence of two configurations is defined by two groups and acting on and , respectively (see [4] and [10]). In this form it is applied, for example, in the determination of the number of non-isomorphic abstract automata.

If , and , where is used as an image times, then the expression

is called the first specification of . If the numbers contain zeros, ones, etc., then the expression

is called the second specification. Under some specification of the groups and defining the equivalence of configurations , it is possible to give a method of constructing generating functions for the enumeration of the inequivalent configurations. This method, called the general combinatorial scheme, can be subdivided into four particular cases, according as the groups and take values in the identity group or the symmetric groups of corresponding orders. These particular cases are the models for the majority of the known combinatorial schemes (see [9], [10]).

1) The commutative non-symmetric case: , . This models combination schemes of distributing identical objects into different cells, etc. The generating function for the enumeration of inequivalent configurations such that

has the form:

2) The non-commutative non-symmetric case: , . This models allocation schemes of distributing distinct objects into different cells, etc. The generating function for the enumeration of inequivalent configurations such that

has the form:

3) The commutative symmetric case: , . This models schemes of distributing identical objects into identical cells, the enumeration of the partitions of natural numbers, etc. The enumeration of configurations such that

is based on the use of generating functions of the form:

4) The non-commutative symmetric case: , . This models schemes of partitioning finite sets into blocks, distributing distinct objects into identical cells, etc. The enumeration of configurations such that

is based on the use of generating functions of the form:

An important place in combinatorial analysis is taken up by asymptotic methods. They are applied both for the simplification of complex finite expressions for large values of the parameters entering into them, as well as for obtaining approximate formulas in roundabout ways when the exact formulas are unknown. It is sometimes convenient to formulate a combinatorial problem of an enumerative character as a problem of finding the characteristics of the distribution of some random process. Such an interpretation makes it possible to apply the well-developed apparatus of probability theory for finding asymptotics or limit theorems. Classical schemes of random allocations of objects in cells are open to a detailed investigation from these points of view; so also are random partitions of sets, the cyclic structure of random permutations, as well as various classes of random graphs, including graphs of mappings (see [8], [9], [11]).

The probabilistic approach is applied in the study of the combinatorial properties of symmetric groups and semi-groups. The limiting distribution of the order of a random element of the symmetric group as has been investigated, as also have the asymptotics of the probability of the generation of random elements of them. For certain classes of random non-negative matrices, the distributions have been studied of the number of zero rows in a matrix and in permanents, and estimates have been given of the probability of the primitiveness of such matrices. For the proof of the existence of combinatorial configurations without constructing them, one sometimes employs a certain specific probabilistic device. The essence of this device consists in the proof of the existence of the configuration (without constructing it) by means of an estimate of the probability of some event (see [7]).

References

[1]	J. Riordan, "An introduction to combinational analysis" , Wiley (1958)
[2]	H.J. Ryser, "Combinatorial mathematics" , Carus Math. Monogr. , 14 , Math. Assoc. Amer. (1963)
[3]	M. Hall, "Combinatorial theory" , Blaisdell (1967)
[4]	E.F. Beckenbach (ed.) , Applied combinatorial mathematics , Wiley (1964)
[5]	F. Harary, "Graph theory" , Addison-Wesley (1969) pp. Chapt. 9
[6]	F Harary, E. Palmer, "Graphical enumeration" , Acad. Press (1973)
[7]	P. Erdös, J. Spencer, "Probabilistic methods in combinatorics" , Acad. Press (1974)
[8]	V.F. Kolchin, V.P. Chistyakov, "Combinatorial problems of probability theory" Itogi Nauk. i Tekhn. Teor. Veroyatnost. Mat. Stat. Teoret. Kibernet. , 11 (1974) pp. 5–45 (In Russian)
[9]	V.N. Sachkov, , Questions of cybernetics. Proc. Seminar on Combinatorial Mathematics , Moscow (1973) pp. 146–164 (In Russian)
[10]	V.N. Sachkov, "Combinatorial methods in discrete mathematics" , Moscow (1977) (In Russian)
[11]	V.N. Sachkov, "Probabilistic methods in combinatorial analysis" , Moscow (1978) (In Russian)
[12]	H. Minc, "Permanents" , Addison-Wesley (1978)
[13]	G.P. [G.P. Egorichev] Egorychev, "The solution of van der Waerden's problem for permanents" Adv. in Math. , 42 : 3 (1981) pp. 299–305

Comments

The marriage problem is the following. Let there be a set of girls and a set of boys. Each girl likes a subset of boys. When is it possible that each girl marries a boy she likes? The solution is of course given by the P. Hall theorem on distinct representatives, and this theorem is also known as the marriage theorem or the P. Hall marriage theorem. The abbreviation SDR is often used for systems of distinct representatives. Let be the bipartite graph (cf. Graph, bipartite) consisting of the vertices and with an edge joining and if and only if girl likes boy (and no other edges). Then a solution of the marriage problem provides a matching, and in this context the marriage theorem is also known as the P. Hall matching theorem.

A good up-to-date book on design theory is [a1]. For more on extremal problems in graph theory cf. [a2]. For more on the dimer problem and other uses of combinatorics in theoretical physics cf., e.g., [a3]. Finally, [a4] is completely devoted to transversal theory including infinite versions.

References

[a1]	D.R. Hughes, F.C. Piper, "Design theory" , Cambridge Univ. Press (1985)
[a2]	B. Bollobas, "Extremal graph theory" , Acad. Press (1978)
[a3]	J.K. Percus, "Combinatorial methods" , Springer (1971)
[a4]	L. Mirsky, "Transversal theory" , Acad. Press (1971)