Also found in: Dictionary.
combinatorial analysis[kəm‚bī·nə′tȯr·ē·əl ə′nal·ə·səs]
(also combinatorial mathematics, combinatorics), a branch of mathematics that studies problems of permutations and mutual arrangements of parts of a finite set of objects of arbitrary nature (as well as infinite sets satisfying certain finiteness conditions).
Ideas of a combinatorial nature are used most extensively in mathematics in such branches as probability theory, number theory, and algebra. Problems of combinatorial analysis were already known in antiquity. Many mathematicians contributed to the development of combinatorial analysis. However, only in the 20th century did it begin to take shape as an independent scientific discipline. Combinatorial analysis is closely connected with the theory of graphs, the theory of finite automata, and other branches of mathematics. Its results are used in the design and analysis of scientific experiments, information coding, linear and dynamic programming, mathematical economics, and many other areas of science and technology.
There are three types of combinatorial-analysis problems.
(1) Enumeration problems. Problems of this type involve finding the number of possible arrangements of a finite set of objects satisfying various conditions. A typical example is the problem of the arrangement of n particles in N boxes. The particles and the boxes may be either distinguishable or not (with correspondingly different results). Powerful methods have been developed for the solution of the various kinds of enumeration problems encountered in practice; among these the method of generating functions and Polya’s method of enumeration are fundamental.
(2) Problems of existence and construction. Of interest in problems of this type is whether there exists a configuration of the parts of a finite set that possesses certain given properties, and if so, how to construct it. For example, does a system of subsets (blocks) of a given finite set exist in which any two distinct elements of the set occur together in these blocks a given number of times. Such systems are called block-schemes. These and similar configurations are intensively studied in combinatorial analysis. Number-theoretical and algebraic methods play an important role in these problems.
(3) Selection problems. Problems of this type study conditions under which it is possible to choose a subset or a certain aggregate of parts of a set in such a way that certain requirements are satisfied. These requirements are usually of an optimizing nature. For example, let a set be given and let there exist a certain system of subsets. We ask under what conditions is it possible to select a single element from each subset such that all these elements are pairwise distinct? This is a problem concerning a system of different representatives for a system of subsets. In the solution of selection problems one uses algebraic as well as purely combinatorial considerations.
REFERENCESRiordan, J. Vvedenie v kombinatornyi analiz. Moscow, 1963. (Translated from English.)
Ryser, H. J. Kombinatornaia matematika. Moscow, 1966. (Translated from English.)
V. E. TARAKANOV (12–1465–4]