Combinatorial Analysis


Also found in: Dictionary, Wikipedia.

combinatorial analysis

[kəm‚bī·nə′tȯr·ē·əl ə′nal·ə·səs]
(mathematics)
The determination of the number of possible outcomes in ideal games of chance by using formulas for computing numbers of combinations and permutations.
The study of large finite problems.

Combinatorial Analysis

 

(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.

REFERENCES

Riordan, 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]

References in periodicals archive ?
12) As such, the combinatorial analysis appears to have a slightly stronger ability to capture the underlying systematic tendency hypothesized in this paper, but the difference is not significant.
The combinatorial analysis indicated that expected relative score mattered, that the purse mattered, but that the expected earnings (which captures the strength of the rest of the field) did not matter.
where the three effects examined separately in the combinatorial analysis can be simultaneously considered.
The results confirm the inferences derived from the combinatorial analysis.
A combinatorial analysis compared the subset of tournaments chosen to the random distribution of possible subsets.
Based on the regression analysis, the results pictured in Figure 6 and listed in Table 4 confirm and extend those of the combinatorial analysis.
The combinatorial analysis illustrated in Figure 5 shows that there is no support for the proposition that golfers choose based on "expected" prize earnings which depend on the size of the purse and the number of other contestants likely to place above the golfer in question.
The results confirm and strengthen the results of the combinatorial analysis.
05) in the combinatorial analysis are not also significant in the regression.

Full browser ?