COMBINATORI AL earliest algebraists, but the true pioneer of modem researches seems to have been Abraham Demoivre, who first published in 1697 (Phil. Trans, li. S.) the law of the general coefficient in the expansion of the series a + bx + cx* + dxz + ... raised to any power. (See also Miscellanea Analytica, Bk. iv. chap. ii. prob. iv.) His work on Probabilities would naturally lead him to consider questions of this nature. An important work at the time it was published was the De Partitione Numerorum of Euler, in which the consideration of the reciprocal of the product (1 - xz){ -#‘2z)(l -xsz)... establishes a fundamental connexion between arithmetic and algebra, arithmetical addition being made to depend upon algebraical multiplication, and a close bond is secured between the theories of discontinuous and continuous quantities. The multiplication of the two powers xa, xb, viz., xa x xb = xa+b showed Euler that he could convert arithmetical addition into algebraical multiplication, and in the paper referred to he gives the complete formal solution of the 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 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 special problems are James Bernouilli, Boscovitch, Hindenburgh, Emerson, Woodhouse, Simpson, and Barlow. Problems of combination were generally undertaken as they became necessary for the advancement of some particular part of mathematical science : it was not recognized that the theory of combinations is in reality a science by itself, well worth studying for its own sake irrespective of applications to other parts of analysis. There was a total absence of orderly development, and until the first third of the 19 th century had passed, Euler’s classical paper remained alike the chief result and the only scientific method of combinatorial analysis. In 1846 Jacobi studied the partitions of numbers by means of certain identities involving infinite series that are met with in the theory of Elliptic Functions. The method employed is essentially that of Euler. Interest in England was aroused, in the first instance, by De Morgan in 1846, who, in a letter to Henry Warburton, suggested that combinatorial analysis stood in 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 instrument, viz., the theory of finite 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. Camb. Phil. Soc., 1849). This paper inspired a valuable paper by Sir John Herschel {Phil. Trans. Roy. Soc., 1850), who, by introducing the idea and notation of the circulating function, was able to 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 Cayley and Sylvester, and their combined efforts resulted in the practical solution of the problem that we have to-day. The former added the idea of the prime circulator, and the latter applied Cauchy’s theory of Residues to the subject, and invented the arithmetical entity termed a “ denumerant.” The next distinct advance was made by Sylvester, Franklin, Durfee, and others, about the 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 light upon the theory of algebraic series. So far it will be seen that researches had for their object the discussion of the
ANALYSIS
153
partition of numbers. Other branches of combinatorial analysis were, from any general point of view, absolutely neglected. In 1888 MacMahon investigated the general problem of distribution, of which the partition of a number is a particular case. He introduced the method of symmetric functions and the method of differential operators, applying both methods to the two important subdivisions, the theory of 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. Mathews, which reduces the problem of compound partition to that of 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 Rule of Ceres”; it is only now, nearly 200 years later, that it has been solved. The most important problem of combinatorial analysis is connected with the distribution of objects into classes. A number n may be regarded as enumerating n similar objects ; it is then said to be unipartite. F™ntal On the other hand, if the objects be not all probfem. similar they cannot be effectively enumerated by a single integer; we require a succession of integers. If the objects be p in number of one kind, g 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 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 px of one s kind, qx of a second, rx of a third, &c., where p1 + ql- rrl + ...—m. We may thus denote the classes either by the multipartite numbers pyq^ ..., or by the partition {pxqxrx ... ) 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 parcel; if the order is material the class is termed a 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 {p-flir^ ... ) of the number m. (See “Symmetric Functions and the Theory of Distributions,” Proc. 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 (1111 ... ), conS. III.— 20
