Online Encyclopedia

Search over 40,000 articles from the original, classic Encyclopedia Britannica, 11th Edition.

COMBINATORIAL ANALYSIS

Online Encyclopedia
Originally appearing in Volume V06, Page 753 of the 1911 Encyclopedia Britannica.
» Make a correction to this article.
» Add information or comments to this article.
Spread the word: del.icio.us del.icio.us it!

COMBINATORIAL See also:

ANALYSIS . The Combinatorial Analysis, as it was understood up to the end of the 18th See also:century, was of limited See also:scope and restricted application. P. See also:Nicholson, Historkai in his Essays on the Combinatorial Analysis, published intro- See also:auction. in 1818, states that " the Combinatorial Analysis is a See also:branch of See also:mathematics which teaches us to ascertain and exhibit all the possible ways in which a given number of things may be associated and mixed together; so that we may be certain that we have not missed any collection or arrangement of these things that has not been enumerated." Writers on the subject seemed to recognize fully that it was in need of cultiva- tion, that it was of much service in facilitating algebraical operations of all kinds, and that it was the fundamental method of investigation in the theory of Probabilities. Some See also:idea of its scope may be gathered from a statement of the parts of See also:algebra to which it was commonly applied, viz., the expansion of a . multinomial, the product of two or more multinomials, the quotient of one multinomial by another, the reversion and See also:conversion of See also:series, the theory of indeterminate equations, &c. Some of the elementary theorems and various particular problems appear in the See also:works of the earliest algebraists, but the true See also:pioneer of See also:modern researches seems to have been See also:Abraham See also:Demoivre, who first published in Phil. Trans. (1697) the See also:law of the See also:general coefficient in the expansion of the series a+bx+cx2+dx3+ . . . raised to any See also:power. (See also Miscel- lanea Analytica, bk. iv. See also:chap. ii. prob. iv.) His See also:work on Proba- bilities would naturally See also:lead him to consider questions of this nature. An important work at the See also:time it was pub- lished was the De See also:Partition Numerorum of Leonhard See also:Euler, in which the See also:consideration of the reciprocal of the product (I— xz) (1— x2z) (1—x3z) . . . establishes a fundamental connexion between See also:arithmetic and algebra, arithmetical addition being made to depend upon algebraical multiplication, and a See also:close See also:bond is secured between the theories of discontinuous and continuous quantities.

(Cf. See also:

NUMBERS, PARTITION OF.) The multiplication of the two See also:powers x°, xb, viz. x°-i-xb=e+a, showed Euler that he could convert arithmetical addition into algebraical multiplication, and in the See also:paper referred to he gives the See also:complete formal See also:solution of the See also:main problems of the partition of numbers. He did not obtain general expressions for the coefficients which arose in the expansion of his generating functions, but he gave the actual values to a high See also:order of the coefficients which arise from the generating functions corresponding to various conditions of partitionment. Other writers who have contributed to the solution of See also:special problems are See also:James See also:Bernoulli, Ruggiero Guiseppe See also:Boscovich, Karl See also:Friedrich Hindenburg (1741—1808), See also:William See also:Emerson (1701—1782), See also:Robert Woodhouse (1773—1827), See also:Thomas See also:Simpson and See also:Peter See also:Barlow. Problems of See also:combination were generally undertaken as they became necessary for the See also:advancement of some particular See also:part of mathematical See also:science: it was not recognized that the theory of combinations is in reality a science by itself, well See also:worth studying for its own See also:sake irrespective of applications to other parts of analysis. There was a See also:total See also:absence of orderly development, and until the first third of the 19th century had passed, Euler's classical paper remained alike the See also:chief result and the only scientific method of combinatorial analysis. In 1846 Karl G. J. See also:Jacobi studied the partitions of numbers by means of certain identities involving See also:infinite series that are met with in the theory of elliptic functions. The method employed is essentially that of Euler. See also:Interest in See also:England was aroused, in the first instance, by See also:Augustus De See also:Morgan in 1846, who, in a See also:letter to See also:Henry See also:Warburton, suggested that combinatorial analysis stood in See also:great need of development, and alluded to the theory of partitions. Warburton, to some extent under the guidance of De Morgan, prosecuted researches by the aid of a new See also:instrument, viz. the theory of finite See also:differences.

This was a distinct advance, and he was able to obtain expressions for the coefficients in partition series in some of the simplest cases (Trans. Carob. Phil. See also:

Soc., 1849). This paper inspired a valuable paper by See also:Sir See also:John See also:Herschel (Phil. Trans. 185o), who, by introducing the idea and notation of the circulating See also:function, was able to See also:present results in advance of those of Warburton. The new idea involved a calculus of the imaginary roots of unity. Shortly afterwards, in 1855, the subject was attacked simultaneously by See also:Arthur See also:Cayley and James See also:Joseph See also:Sylvester, and their combined efforts resulted in the See also:practical solution of the problem that we have to-See also:day. The former added the idea of the See also:prime circulator, and the latter applied See also:Cauchy's theory of residues to the subject, and invented the arithmetical entity termed a denumerant. The next distinct advance was made by Sylvester, See also:Fabian See also:Franklin, William See also:Pitt Durfee and others, about the See also:year 1882 (Amer. Journ.

Math. vol. v.) by the employment of a graphical method. The results obtained were not only valuable in themselves, but also threw considerable See also:

light upon the theory of algebraic series. So far it will be seen that researches had for their See also:object the discussion of the partition of numbers. Other branches of combinatorial analysis were, from any general point of view, absolutely neglected. In 1888 P. A. See also:MacMahon investigated the general problem of See also:distribution, of which the partition of a number is a particular See also:case. He introduced the method of symmetric functions and the method of See also:differential operators, applying both methods to the two important subdivisions, the theory of See also:composition and the theory of partition. He introduced the notion of the separation of a partition, and extended all the results so as to include multipartite as well as unipartite numbers. He showed how to introduce zero and negative numbers, unipartite and multipartite, into the general theory he extended Sylvester's graphical method to three dimensions; and finally, 1898, he invented the "Partition Analysis" and applied it to the solution of novel questions in arithmetic and algebra. An important paper by G. B.

See also:

Mathews, which reduces the problem of See also:compound partition to that of See also:simple partition, should also be noticed. This is the problem which was known to Euler and his contemporaries as "The Problem of the Virgins," or "the See also:Rule of See also:Ceres "; it is only now, nearly 200 years later, that it has been solved. The most important problem of combinatorial analysis is See also:con- nected with the distribution of See also:objects into classes. A number n may be regarded as enumerating n similar objects; it See also:Panda- is then said to be unipartite. On the other See also:hand, if the See also:mental objects be not all similar they cannot be effectively enu- probiem. merated by a single integer; we require a See also:succession of integers. If the objects be p in number of one See also:kind, q of a second kind, r of a third, &c., the enumeration is given by the succession pqr . . . which is termed a multipartite number, and written, pqr..., where p+q+r+ . . . =n. If the order of magnitude of the numbers p, q, r, . . . is immaterial, it is usual to write them in descending order of magnitude, and the succession may then be termed a partition of the number n, and is written (pqr ...).

The succession of integers thus has a twofold signification: (i.) as a multipartite number it may enumerate objects of different kinds; (ii.) it may be viewed as a partitionment into See also:

separate parts of a unipartite number. We may say either that the objects are represented by the multipartite number pqr ..., or that they are defined by the partition (pqr . . . ) of the unipartite number n. Similarly the classes into which they are distributed may be m in number all similar; or they may be pi of one kind, qi of a second, r1 of . a third, &c., where pi + qi +ri + ... = m. We may thus denote the classes either by the multipartite numbers plgirl . . ., or by the partition (pigiri . . . ) of the unipartite number m. The distributions to be considered are such that any number of objects may be in any one class subject to the restriction that no class is empty. Two cases arise.

If the order of the objects in a particular class is immaterial, the class is termed a See also:

parcel; if the order is material, the class is termed a See also:group. The distribution into parcels is alone considered here, and the main problem is the enumeration of the distributions of objects defined by the partition (pqr ... ) of the number n into parcels defined by the partition (pigiri ... ) of the number m. (See "Symmetric Functions and the Theory of Distributions," Proc. See also:London Mathematical Society, vol. xix.) Three particular cases are of great importance. Case I. is the " one-to-one distribution," in which the number of parcels is equal to the number of objects, and one object is distributed in each parcel. Case II. is that in which the parcels are all different, being defined by the partition (till . . . ), conveniently written (1'") ; this is the theory of the compositions of unipartite arid multipartite numbers. Case III. is that in which the parcels are all similar, being defined by the partition (m); this is the theory of the partitions of unipartite and multipartite numbers. Previous to discussing these in detail, it is necessary to describe the method of symmetric functions which will be largely utilized.

Let a, /3, y, ... be the roots cf the See also:

equation x'—aixn_i+a2xn E—...=o. The symmetric function Ea5/3°yr..., where p+q+r+ ... =n is, in the partition notation, written (pqr . . . ). Let A(PQr (p e rl ) denote the number of ways of distri- buting the n objects defined by the partition (pqr . ) into the m parcels defined by the partition (pigiri . . . ).

End of Article: COMBINATORIAL ANALYSIS

Additional information and Comments

There are no comments yet for this article.
» Add information or comments to this article.
Please link directly to this article:
Highlight the code below, right click, and select "copy." Then paste it into your website, email, or other HTML.
Site content, images, and layout Copyright © 2006 - Net Industries, worldwide.
Do not copy, download, transfer, or otherwise replicate the site content in whole or in part.

Links to articles and home page are always encouraged.

[back]
COMBINATION (Lat. combinare, to combine) 		[next]
COMBUSTION (from the Lat. comburere, to burn up)

Site © 2006 - Net Industries