# 1911 Encyclopædia Britannica/Combinatorial Analysis

See also Combinatorial data analysis on Wikipedia; and our 1911 Encyclopædia Britannica disclaimer.
​COMBINATORIAL ANALYSIS. The Combinatorial Analysis, as it was understood up to the end of the 18th century, was of limited scope and restricted application. P. Nicholson, in his Essays on the Combinatorial Analysis, published in 1818, states that “the Combinatorial Analysis is a branch of mathematics which teaches us to ascertain Historical Introduction. 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 cultivation, 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 idea of its scope may be gathered from a statement of the parts of 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 conversion of series, the theory of indeterminate equations, &c. Some of the elementary theorems and various particular problems appear in the works of the earliest algebraists, but the true pioneer of modern researches seems to have been Abraham Demoivre, who first published in Phil. Trans. (1697) the law of the general coefficient in the expansion of the series a + bx + cx² + dx³ + . . . 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 Leonhard Euler, in which the consideration of the reciprocal of the product (1 − xz) (1 − x²z) (1 − x³z) . . . 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. (Cf. Numbers, Partition of.) The multiplication of the two powers x$^a$, x$^b$, viz. x$^a$ + x$^b$ = x$^{a+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 Bernoulli, Ruggiero Guiseppe Boscovich, Karl Friedrich Hindenburg (1741–1808), William Emerson (1701–1782), Robert Woodhouse (1773–1827), Thomas Simpson and Peter 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 19th century had passed, Euler’s classical paper remained alike the chief result and the only scientific method of combinatorial analysis.
In 1846 Karl G. J. 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 Augustus 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. 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 Arthur Cayley and James Joseph 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, Fabian Franklin, William Pitt 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 partition of numbers. Other branches of combinatorial analysis were, from any general point of view, absolutely neglected. In 1888 P. A. 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. On the other hand, if the objects be not all similar they cannot be effectively enumerated Fundamental problem. by a single integer; we require a succession of integers. If the objects be p in number of one 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 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 p$_1$ of one kind, q$_1$ of a second, r$_1$ of a third, &c., where p$_1$ + q$_1$ + r$_1$ + . . . = m. We may thus denote the classes either by the multipartite numbers ________ p$_1$q$_1$r$_1$ . . ., or by the partition (p$_1$q$_1$r$_1$ . . . ) 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$_1$q$_1$r$_1$ . . . ) 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. . .), conveniently written (1$^m$); this is the theory of the compositions of unipartite and 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 α, β, γ, . . . be the roots of the equation
x$^n$ − a$_1$x$^{n−1}$ + a$_2$x$^{n−2}$ − . . . = 0
The symmetric function Σα$^p$β$^q$γ$^r$..., where p + q + r + ... = n is, in the partition notation, written (pqr . . .). Let A$_{(pqr...),(p1q1r1...)}$ denote the number of ways of distributing the n objects defined by the partition (pqr . . .) into the m parcels defined by the partition (p$_1$q$_1$r$_1$ . . . ). The distribution function. The expression
ΣA$_{(pqr...),(p1q1r1...)}$ · (pqr. . .),
where the numbers p$_1$, q$_1$, r$_1$ . . . are fixed and assumed to be in descending order of magnitude, the summation being for every partition (pqr. . .) of the number n, is defined to be the distribution function of the objects defined by (pqr. . .) into the parcels defined by (p$_1$q$_1$r$_1$ . . . ). It gives a complete enumeration of n objects of whatever species into parcels of the given species.
1. One-to-One Distribution. Parcels m in number (i.e. m = n).—Let h$_s$ be the homogeneous product-sum of degree s of the quantities α, β, γ, . . . so Case I.that
(1 − αx. 1 − βx. 1 − γx. ...)$^{−1}$ = 1 + h$_1$x + h$_2$x$^2$ + h$_3$x$^3$ + ...
* h$_1$ = Σα = (1)
* h$_2$ = Σα$^2$ + Σαβ = (2) + (1$^2$)
* h$_3$ = Σα$^3$ + Σα$^2$β + Σαβγ = (3) + (21) + (1$^3$).
Form the product h$_{p1}$h$_{q1}$h$_{r1}$...
Any term in h$_{p1}$ may be regarded as derived from p$_1$ objects distributed into p$_1$ similar parcels, one object in each parcel, since the order of occurrence of the letters α, β, γ, . . . in any term is immaterial. Moreover, every selection of p$_1$ letters from the letters in α$^p$β$^q$γ$^r$ . . . will occur in some term of h$_{p1}$, every further selection of q$_1$ letters will occur in some term of h$_{q1}$, and so on. Therefore in the product h$_{p1}$h$_{q1}$h$_{r1}$ . . . the term α$^p$β$^q$γ$^r$ . . ., and therefore also the symmetric function (pqr . . .), will occur as many times as it is possible to distribute objects defined by (pqr . . .) into parcels defined by (p$_1$q$_1$r$_1$ . . .) one object in each parcel. Hence
ΣA$_{(pqr...),(p1q1r1...)}$ · (pqr . . .)＝h$_{p1}$h$_{q1}$h$_{r1}$ ....
This theorem is of algebraic importance; for consider the simple particular case of the distribution of objects (43) into parcels (52), and represent objects and parcels by small and capital letters respectively. One distribution is shown by the scheme
wherein an object denoted by a small letter is placed in a parcel denoted by the capital letter immediately above it. We may interchange small and capital letters and derive from it a distribution of objects (52) into parcels (43); viz.:—
The process is clearly of general application, and establishes a one-to-one correspondence between the distribution of objects (pqr . . .) into parcels (p$_1$q$_1$r$_1$ . . .) and the distribution of objects (p$_1$q$_1$r$_1$ . . .) into parcels (pqr . . .). It is in fact, in Case I., an intuitive observation that we may either consider an object placed in or attached to a parcel, or a parcel placed in or attached to an object. Analytically we have
Theorem.—“The coefficient of symmetric function (pqr . . .) in the development of the product h$_{p1}$h$_{q1}$h$_{r1}$ . . . is equal to the coefficient of symmetric function (p$_1$q$_1$r$_1$ . . .) in the development of the product h$_p$h$_q$h$_r$ . . .”
The problem of Case I. may be considered when the distributions are subject to various restrictions. If the restriction be to the effect that an aggregate of similar parcels is not to contain more than one object of a kind, we have clearly to deal with the elementary symmetric functions a$_1$, a$_2$, a$_3$, . . . or (1), (1$^2$), (1$^3$), . . . in lieu of the quantities h$_1$, h$_2$, h$_3$, . . . The distribution function has then the value a$_{p1}$a$_{q1}$a$_{r1}$... or (1$^p$$_1$) (1$^q$$_1$) (1$^r$$_1$) ..., and by interchange of object and parcel we arrive at the well-known theorem of symmetry in symmetric functions, which states that the coefficient of symmetric function (pqr . . .) in the development of the product a$_{p1}$a$_{q1}$a$_{r1}$ . . . in a series of monomial symmetric functions, is equal to the coefficient of the function (p$_1$q$_1$r$_1$ . . .) in the similar development of the product a$_p$a$_q$a$_r$ . . . .
The general result of Case I. may be further analysed with important consequences.
Write
* X$_1$ = (1)x$_1$,
* X$_2$ = (2)x$_2$ + (1$^2$)x2 1,
* X$_3$ = (3)x$_3$ + (21)x$_2$x$_1$ + (1$^3$)x3 1
the summation being in regard to every partition of s. Consider the result of the multiplication—
X$_{p1}$X$_{q1}$X$_{r1}$ ... = ΣP$x_{s_{1}}^{\sigma _{1}}x_{s_{2}}^{\sigma _{2}}x_{s_{3}}^{\sigma _{3}}...$
To determine the nature of the symmetric function P a few definitions are necessary.
Definition I.—Of a number n take any partition (λ$_1$λ$_2$λ$_3$ . . . λ$_s$) and separate it into component partitions thus:—
(λ$_1$λ$_2$) (λ$_3$λ$_4$λ$_5$) (λ$_6$)...
in any manner. This may be termed a separation of the partition, the numbers occurring in the separation being identical with those which occur in the partition. In the theory of symmetric functions the separation denotes the product of symmetric functions—
Σα$^{λ1}$β$^{λ2}$Σα$^{λ3}$β$^{λ4}$γ$^{λ5}$Σα$^{λ6}$...
The portions (λ$_1$λ$_2$), (λ$_3$λ$_4$λ$_5$), (λ$_6$), . . . are termed separates, and if λ$_1$ + λ$_2$ = p$_1$, λ$_3$ + λ$_4$ + λ$_5$ = q$_1$, λ$_6$ = r$_1$. . . be in descending order of magnitude, the usual arrangement, the separation is said to have a species denoted by the partition (p$_1$q$_1$r$_1$ ...) of the number n.
Definition II.—If in any distribution of n objects into n parcels (one object in each parcel), we write down a number ξ, whenever we observe ξ similar objects in similar parcels we will obtain a succession of numbers ξ$_1$, ξ$_2$, ξ$_3$,. . ., where (ξ$_1$, ξ$_2$, ξ$_3$. . .) is some partition of n. The distribution is then said to have a specification denoted by the partition (ξ$_1$ξ$_2$ξ$_3$. . .).
Now it is clear that P consists of an aggregate of terms, each of which, to a numerical factor près, is a separation of the partition ${\bigs_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}$ of species (p$_1$q$_1$r$_1$. . .). Further, P is the distribution function of objects into parcels denoted by (p$_1$q$_1$r$_1$. . .), subject to the restriction that the distributions have each of them the specification ​denoted by the partition ${\bigs_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}.$ Employing a more general notation we may write
Xπ$_1$ p$_1$ Xπ$_2$ p$_2$ Xπ$_3$ p$_3$ ... = ΣPxσ$_1$ s$_1$ xσ$_2$ s$_2$ xσ$_3$ s$_3$ ...
and then P is the distribution function of objects into parcels (pπ$_1$ 1 pπ$_2$ 2 pπ$_3$ 3 ...), the distributions being such as to have the specification ${\bigs_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}.$. Multiplying out P so as to exhibit it as a sum of monomials, we get a result—
Xπ$_1$ p$_1$ Xπ$_2$ p$_2$ Xπ$_3$ p$_3$ ... = ΣΣθ (λl$_1$ 1 λl$_2$ 2 λl$_3$ 3 ...) xσ$_1$ s$_1$ xσ$_2$ s$_2$ xσ$_3$ s$_3$ ...
indicating that for distributions of specification ${\bigs_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}.$. there are θ ways of distributing n objects denoted by (λl$_1$ 1 λl$_2$ 2 λl$_3$ 3 ...) amongst n parcels denoted by (p$^{π1}$$_1$ p$^{π2}$$_2$ p$^{π3}$$_3$ ...), one object in each parcel. Now observe that as before we may interchange parcel and object, and that this operation leaves the specification of the distribution unchanged. Hence the number of distributions must be the same, and if
then also
X$^{l1}$$_{λ1}$ X$^{l2}$$_{λ2}$ X$^{l3}$$_{λ3}$ ... = ... + θ (p$^{π1}$$_1$ p$^{π2}$$_2$ p$^{π3}$$_3$ ...) xσ$_1$ s$_1$ xσ$_2$ s$_2$ xσ$_3$ s$_3$ ... + ...
This extensive theorem of algebraic reciprocity includes many known theorems of symmetry in the theory of Symmetric Functions.
The whole of the theory has been extended to include symmetric functions symbolized by partitions which contain as well zero and negative parts.
2. The Compositions of Multipartite Numbers. Parcels denoted by (I$^m$).—There are here no similarities between the parcels.
Case II.
Let (π$_1$ π$_2$ π$_3$) be a partition of m.
(pπ$_1$ 1 pπ$_2$ 2 pπ$_3$ 3 ...) a partition of n.
Of the whole number of distributions of the n objects, there will be a certain number such that n$_1$ parcels each contain p$_1$ objects, and in general π$_s$ parcels each contain p$_s$ objects, where s = 1, 2, 3, ... Consider the product hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ... which can be permuted in m!/π$_1$!π$_2$!π$_3$! ... ways. For each of these ways hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ... will be a distribution function for distributions of the specified type. Hence, regarding all the permutations, the distribution function is
| m! | hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ... |
| π$_1$!π$_2$!π$_3$! ... | hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ... |
and regarding, as well, all the partitions of n into exactly m parts, the desired distribution function is
| Σ | m! | hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ...   [Σπ = m, Σπp = n], |
| Σ | π$_1$!π$_2$!π$_3$! ... | hπ$_1$ p$_1$ hπ$_2$ p$_2$ hπ$_3$ p$_3$ ...   [Σπ = m, Σπp = n], |
that is, it is the coefficient of x$^n$ in (h$_1$x + h$_2$x² + h$_3$x³ + ... )$^m$. The value of A$_{(pπ11pπ22pπ33...),(1m)}$ is the coefficient of (p$^{π1}$1 p$^{π2}$2 p$^{π3}$3 ...)x$^n$ in the development of the above expression, and is easily shown to have the value
| | | | | ( | p$_1$ + m − 1 | ) | $^{π1}$ | ( | p$_2$ + m − 1 | ) | $^{π2}$ | ( | p$_3$ + m − 1 | ) | $^{π3}$ | ... |
| | | | | ( | p$_1$ | ) | | ( | p$_2$ | ) | | ( | p$_3$ | ) | | ... |
| − | ( | m | ) | ( | p$_1$ + m − 2 | ) | $^{π1}$ | ( | p$_2$ + m − 2 | ) | $^{π2}$ | ( | p$_3$ + m − 2 | ) | $^{π3}$ | ... |
| − | ( | 1 | ) | ( | p$_1$ | ) | | ( | p$_2$ | ) | | ( | p$_3$ | ) | | ... |
| + | ( | m | ) | ( | p$_1$ + m − 3 | ) | $^{π1}$ | ( | p$_2$ + m − 3 | ) | $^{π2}$ | ( | p$_3$ + m − 3 | ) | $^{π3}$ | ... |
| + | ( | 2 | ) | ( | p$_1$ | ) | | ( | p$_2$ | ) | | ( | p$_3$ | ) | | ... |
| − ... to m terms. |||||||||||||||||
Observe that when p$_1$ = p$_2$ = p$_3$ = ... = π$_1$ = π$_2$ = π$_3$ ... = 1 this expression reduces to the mth divided differences of 0$^n$. The expression gives the compositions of the multipartite number p$^{π1}$$_1$ p$^{π2}$$_2$ p$^{π3}$$_3$ ... into m parts. Summing the distribution function from m = 1 to m = ∞ and putting x = 1, as we may without detriment, we find that the totality of the compositions is given by h$_1$ + h$_2$ + h$_3$ + .../ 1 − h$_1$ − h$_2$ − h$_3$ + ... which may be given the form a$_1$ − a$_2$ + a$_3$ − .../1 − 2(a$_1$ − a$_2$ + a$_3$ − ...). Adding 1/2 we bring this to the still more convenient form
| 1/2 | 1 | . |
| 1/2 | 1 − 2(a$_1$ − a$_2$ + a$_3$ − ...) | . |
Let F (p$^{π1}$$_1$ p$^{π2}$$_2$ p$^{π3}$$_3$ ... ) denote the total number of compositions of the multipartite p$^{π1}$$_1$ p$^{π2}$$_2$ p$^{π3}$$_3$ .... Then 1/2 1/1 − 2a = 1/2 + Σ F(p)α$^p$, and thence F(p) = 2$^{p−1}$. Again 1/2 · 1/1 − 2(α + β − αβ) = Σ F(p$_1$p$_2$) α$^{p1}$β$^{p2}$, and expanding the left-hand side we easily find
| F(p$_1$p$_2$) = 2$^{p1+p2−1}$ | (p$_1$ + p$_2$)! | − 2$^{p1+p2−2}$ | (p$_1$ + p$_2$ − 1)! | + 2$^{p1+p2−3}$ | (p$_1$ + p$_2$ − 2)! | − ... |
| F(p$_1$p$_2$) = 2$^{p1+p2−1}$ | 0! p$_1$! p$_2$! | − 2$^{p1+p2−2}$ | 1! (p$_1$ − 1)! (p$_2$ − 1)! | + 2$^{p1+p2−3}$ | 2! (p$_1$ − 2)! (p$_2$ − 2)! | − ... |
We have found that the number of compositions of the multipartite p$_1$p$_2$p$_3$ ... p$_s$ (p$_1$p$_2$p$_3$ ... p$_s$) or of the single term αp$_1$ 1 αp$_2$ 2 αp$_3$ 3 ... αp$_s$ s  in the development according to ascending powers of the algebraic fraction
| 1/2 · | 1 | . |
| 1/2 · | 1 − 2 (Σα$_1$ − Σα$_1$α$_2$ + Σα$_1$α$_2$α$_3$ − ... + (−)$^{s+1}$ α$_1$α$_2$α$_3$ ... α$_s$ | . |
This result can be thrown into another suggestive form, for it can be proved that this portion of the expanded fraction
| 1/2 · | 1 | , |
| 1/2 · | {1 − t$_1$ (2α$_1$ + α$_2$ + ... + α$_s$)} {1 − t$_2$ (2α$_1$ + 2α$_2$ + ... + α$_s$)} ... {1 − t$_s$ (2α$_1$ + 2α$_2$ + ... + 2α$_s$)} | , |
which is composed entirely of powers of
has the expression
| 1/2 · | 1 | , |
| 1/2 · | 1 − 2 (Σt$_1$α$_1$ − Σt$_1$t$_2$α$_1$α$_2$ + Σt$_1$t$_2$t$_3$α$_1$α$_2$α$_3$ − ... + (−)$^{s+1}$t$_1$t$_2$ ... t$_s$α$_1$α$_2$ ... α$_s$) | , |
and therefore the coefficient of α$^{p1}$1 α$^{p2}$2 ... α$^{ps}$s  in the latter fraction, when t$_1$, t$_2$, &c., are put equal to unity, is equal to the coefficient of the same term in the product
1/2 (2α$_1$ + α$_2$ + ... + α$_s$)$^{p1}$ (2α$_1$ + 2α$_2$ + ... + α$_s$)$^{p2}$ ... (2α$_1$ + 2α$_2$ + ... + 2α$_s$)$^{ps}$.
This result gives a direct connexion between the number of compositions and the permutations of the letters in the product αp$_1$ 1 αp$_2$ 2 ... αp$_s$ s . Selecting any permutation, suppose that the letter a$_r$ occurs q$_r$ times in the last p$_r$ + p$_{r+1}$ + ... + p$_s$ places of the permutation; the coefficient in question may be represented by 1/2 Σ2$^{q1+q2+...+qs}$, the summation being for every permutation, and since q$_1$ = p$_1$ this may be written
Ex. Gr.—For the bipartite 22, p$_1$ = p$_2$ = 2, and we have the following scheme:—
| α$_1$ | α$_1$ | α$_2$ | α$_2$ | q$_2$ = 2 |
| α$_1$ | α$_2$ | α$_1$ | α$_2$ | = 1 |
| α$_1$ | α$_2$ | α$_2$ | α$_1$ | = 1 |
| α$_2$ | α$_1$ | α$_1$ | α$_2$ | = 1 |
| α$_2$ | α$_1$ | α$_2$ | α$_1$ | = 1 |
| α$_2$ | α$_2$ | α$_1$ | α$_1$ | = 0 |
Hence
F(22) = 2 (2$^2$ + 2 + 2 + 2 + 2 + 2$^0$) = 26.
We may regard the fraction
| | 1 | , |
| 1/2 · | {1 − t$_1$ (2α$_1$ + α$_2$ + ... + α$_s$)} {1 − t$_2$ (2α$_1$ + 2α$_2$ + ... + α$_s$)} ... {1 − t$_s$ (2α$_1$ + 2α$_2$ + ... + 2α$_s$)} | , |
as a redundant generating function, the enumeration of the compositions being given by the coefficient of
(t$_1$α$_1$)$^{p1}$ (t$_2$α$_2$)$^{p2}$ ... (t$_s$α$_s$)$^{ps}$.
The transformation of the pure generating function into a factorized redundant form supplies the key to the solution of a large number of questions in the theory of ordinary permutations, as will be seen later.
[The transformation of the last section involves a comprehensive theory of Permutations, which it is convenient to discuss shortly The theory of permutations.here.
If X$_1$, X$_2$, X$_3$, ... X$_n$ be linear functions given by the matricular relation
| (a$_{11}$ | a$_{12}$ | ... | a$_{1n}$) |
| a$_{21}$ | a$_{22}$ | ... | a$_{2n}$ |
| a$_{n1}$ | a$_{n2}$ | ... | a$_{nn}$ |
that portion of the algebraic fraction,
| 1 | , |
| (1 − s$_1$X$_1$) (1 − s$_2$X$_2$) ... (1 − s$_n$X$_n$) | , |
which is a function of the products s$_1$x$_1$, s$_2$x$_2$, s$_3$x$_3$, ... s$_n$x$_n$ only is
* 1
* |(1 − a$_{11}$s$_1$x$_1$) (1 − a$_{22}$s$_2$x$_2$) (1 − a$_{33}$s$_3$x$_3$) ... (1 − a$_{nn}$s$_n$x$_n$)|
where the denominator is in a symbolic form and denotes on expansion
1 − Σ |a$_{11}$|s$_1$x$_1$ + Σ |a$_{11}$a$_{22}$|s$_1$s$_2$x$_1$x$_2$ − ... + (–)$^n$ |a$_{11}$a$_{22}$a$_{33}$ ... a$_{nn}$|
where |a$_{11}$|, |a$_{11}$a$_{22}$|, ... |a$_{11}$a$_{22}$, ... a$_{nn}$| denote the several co-axial minors of the determinant
of the matrix. (For the proof of this theorem see MacMahon, “A certain Class of Generating Functions in the Theory of Numbers,” Phil. Trans. R. S. vol. clxxxv. A, 1894). It follows that the coefficient of
xξ$_1$ 1 xξ$_2$ 2 xξ$_n$ n
(a$_{11}$x$_1$ + a$_{12}$x$_2$ + ... + a$_{1n}$x$_n$)$^{ξ1}$ (a$_{21}$x$_1$ + a$_{22}$x$_2$ + ... + a$_{2n}$x$_n$)$^{ξ2}$ ... (a$_{n1}$x$_1$ + a$_{n2}$x$_2$ + ... + a$_{nn}$x$_n$)$^{ξn}$
is equal to the coefficient of the same term in the expansion ascending-wise of the fraction
1/1 − Σ |a$_{11}$|x$_1$ + Σ |a$_{11}$a$_{22}$|x$_1$x$_2$ + (–)$^n$ |a$_{11}$a$_{22}$ ... | x$_1$x$_2$ ... x$_n$.
If the elements of the determinant be all of them equal to unity, we obtain the functions which enumerate the unrestricted permutations of the letters in
xξ$_1$ 1 xξ$_2$ 2 ... xξ$_n$ n ,
viz.
(x$_1$ + x$_2$ + ... − x$_n$)$^{ξ1+ξ2+...+ξn}$
and
| 1 | . |
| 1 − (x$_1$ + x$_2$ + ... + x$_n$) | . |
Suppose that we wish to find the generating function for the enumeration of those permutations of the letters in xξ$_1$ 1 xξ$_2$ 2 ... xξ$_n$ n  which are such that no letter x$_s$ is in a position originally occupied by an x$_3$ for all values of s. This is a generalization of the “Problème des rencontres” or of “derangements.” We have merely to put
a$_{11}$ = a$_{22}$ = a$_{33}$ = ... = a$_{nn}$ = 0
and the remaining elements equal to unity. The generating product is
(x$_1$ + x$_3$ + ... + x$_n$)$^{ξ2}$ ... (x$_1$ + x$_2$ + ... + x$_{n−1}$)$^{ξn}$,
and to obtain the condensed form we have to evaluate the co-axial minors of the invertebrate determinant—
| 0 | 1 | 1 | ... | 1 |
| 1 | 0 | 1 | ... | 1 |
| 1 | 1 | 0 | ... | 1 |
| 1 | 1 | 1 | ... | 0 |
The minors of the 1st, 2nd, 3rd ... nth orders have respectively the values
0 −1 +2 ⫶ (−)$^{n−1}$ (n − 1),
therefore the generating function is
| 1 | ; |
| 1 − Σ x$_1$x$_2$ − 2Σ x$_1$x$_2$x$_3$ − ... − sΣ x$_1$x$_2$ ... x$_{s+1}$ − ... − (n − 1) x$_1$x$_2$ ... x$_n$ | ; |
or writing
(x − x$_1$) (x − x$_2$) ... (x − x$_n$) = x$_n$ − a$_1$x$^{n−1}$ + a$_2$x$^{n−2}$ − ...,
this is
* 1
* 1 − a$_2$ − 2a$_3$ − 3a$_4$ − ... − (n − 1) a$_n$
Again, consider the general problem of “derangements.” We have to find the number of permutations such that exactly m of the letters are in places they originally occupied. We have the particular redundant product
(ax$_1$ + x$_2$ + ... + x$_n$)$^{ξ1}$ (x$_1$ + ax$_2$ + ... + x$_n$)$^{ξ2}$ ... (x$_1$ + x$_2$ + ... + ax$_n$)$^{ξn}$
in which the sought number is the coefficient of a$^m$ x$^{ξ1}$$_1$ x$^{ξ2}$$_2$ ... x$^{ξn}$$_n$. The true generating function is derived from the determinant
| a | 1 | 1 | 1 | . | . | . |
| 1 | a | 1 | 1 | . | . | . |
| 1 | 1 | a | 1 | . | . | . |
| 1 | 1 | 1 | a | . | . | . |
and has the form
* 1
* 1 − aΣ x$_1$ + (a − 1) (a + 1)Σ x$_1$x$_2$ − ... + (−)$^n$ (a − 1)$^{n−1}$ (a + n − 1)x$_1$x$_2$ ... x$_n$.
It is clear that a large class of problems in permutations can be solved in a similar manner, viz. by giving special values to the elements of the determinant of the matrix. The redundant product leads uniquely to the real generating function, but the latter has generally more than one representation as a redundant product, in the cases in which it is representable at all. For the existence of a redundant form, the coefficients of x$_1$, x$_2$, ... x$_1$x$_2$ ... in the denominator of the real generating function must satisfy 2$^n$ − n² + n − 2 conditions, and assuming this to be the case, a redundant form can be constructed which involves n − 1 undetermined quantities. We are thus able to pass from any particular redundant generating function to one equivalent to it, but involving n − 1 undetermined quantities. Assuming these quantities at pleasure we obtain a number of different algebraic products, each of which may have its own meaning in arithmetic, and thus the number of arithmetical correspondences obtainable is subject to no finite limit (cf. MacMahon, loc. cit. pp. 125 et seq.)]
3. The Theory of Partitions. Parcels defined by (m).—When an ordinary unipartite number n is broken up into other numbers, and the order of occurrence of the numbers is immaterial, the collection of numbers is termed a partition of the number n. It is usual to arrange the numbers comprised in the Case III. collection, termed the parts of the partition, in descending order of magnitude, and to indicate repetitions of the same part by the use of exponents. Thus (32111), a partition of 8, is written (321³). Euler’s pioneering work in the subject rests on the observation that the algebraic multiplication
x$^a$ × x$^b$ × x$^c$ × ... x$^{a+b+c+...}$
is equivalent to the arithmetical addition of the exponents a, b, c, ... He showed that the number of ways of composing n with p integers drawn from the series a, b, c, ..., repeated or not, is equal to the coefficient of ζ$^p$x$^n$ in the ascending expansion of the fraction
| 1 | , |
| 1 − ζx$^a$. 1 − ζx$^b$. 1 − ζx$^c$. ... | , |
which he termed the generating function of the partitions in question.
If the partitions are to be composed of p, or fewer parts, it is merely necessary to multiply this fraction by 1/(1 − ζ). Similarly, if the parts are to be unrepeated, the generating function is the algebraic product
(1 + ζx$^a$) (1 + ζx$^b$) (1 + ζx$^c$) ...;
if each part may occur at most twice,
(1 + ζx$^a$ + ζ$^2$x$^{2a}$) (1 + ζx$^b$ + ζ$^2$x$^{2b}$) (1 + ζx$^c$ + ζ$^2$x$^{2c}$) ...;
and generally if each part may occur at most k − 1 times it is
| 1 − ζ$^k$x$^{ka}$ | · | 1 − ζ$^k$x$^{kb}$ | · | 1 − ζ$^k$x$^{kc}$ | · ... |
| 1 − ζx$^a$ | · | 1 − ζx$^b$ | · | 1 − ζx$^c$ | · ... |
It is thus easy to form generating functions for the partitions of numbers into parts subject to various restrictions. If there be no restriction in regard to the numbers of the parts, the generating function is
* 1
* 1 − x$^a$. 1 − x$^b$. 1 − x$^c$. ...
and the problems of finding the partitions of a number n, and of determining their number, are the same as those of solving and enumerating the solutions of the indeterminate equation in positive integers
ax + by + cz + ... = n.
Euler considered also the question of enumerating the solutions of the indeterminate simultaneous equation in positive integers
* ax + by + cz + ... = n
* a′x + b′y + c′z + ... = n′
* a″x + b″y + c″z + ... = n″
which was called by him and those of his time the “Problem of the Virgins.” The enumeration is given by the coefficient of x$^n$y$^{n′}$z$^{n″}$ ... in the expansion of the fraction
* 1
* (1 − x$^a$y$^b$z$^c$ ...) (1 − x$^{a′}$y$^{b′}$z$^{c′}$ ...) (1 − x$^{a″}$y$^{b″}$z$^{c″}$ ...) ...
which enumerates the partitions of the multipartite number nn′n″ ... into the parts
Sylvester has determined an analytical expression for the coefficient of x$^n$ in the expansion of
| 1 | . |
| (1 − x$^a$) (1 − x$^b$) ... (1 − x$^i$) | . |
To explain this we have two lemmas:—
Lemma 1.—The coefficient of x$^{−1}$, i.e., after Cauchy, the residue in the ascending expansion of (1 − e$^x$)$^{−i}$, is −1. For when i is unity, it is obviously the case, and
| (1 − e$^x$)$^{−i−1}$ = (1 − e$^x$)$^{−i}$ + e$^x$(1 − e$^x$)$^{−i−1}$ = (1 − e$^x$)$^{−i}$ + | d | (1 − e$^x$)$^{−i}$ · | 1 | . |
| (1 − e$^x$)$^{−i−1}$ = (1 − e$^x$)$^{−i}$ + e$^x$(1 − e$^x$)$^{−i−1}$ = (1 − e$^x$)$^{−i}$ + | dx | (1 − e$^x$)$^{−i}$ · | i | . |
Here the residue of d/dx (1 − e$^x$)$^{−i}$ · 1/i is zero, and therefore the residue of (1 − e$^x$)$^{−i}$ is unchanged when i is increased by unity, and is therefore always −1 for all values of i.
Lemma 2.—The constant term in any proper algebraical fraction developed in ascending powers of its variable is the same as the residue, with changed sign, of the sum of the fractions obtained by substituting in the given fraction, in lieu of the variable, its exponential multiplied in succession by each of its values (zero excepted, if there be such), which makes the given fraction infinite. For write the proper algebraical fraction
| F(x) = ΣΣ | c$_{λ,μ}$ | + Σ | γλ | . |
| F(x) = ΣΣ | (a$_μ$ − x)λ | + Σ | x$^λ$ | . |
| ΣΣ | c$_{λ,μ}$ | , |
| ΣΣ | a$^λ$ν | , |
Let a$_ν$ be a value of x which makes the fraction infinite. The residue of
| ΣΣΣ | c$_{λ,μ}$ | + Σ | γ$_λ$ |
| ΣΣΣ | (a$_μ$ – a$_ν$e$^x$)$^λ$ | + Σ | a$^λ$ν e$^{λx}$ |
is equal to the residue of
| ΣΣΣ | c$_{λ,μ}$ | , |
| ΣΣΣ | (a$_μ$ – a$_ν$e$^x$)$^λ$ | , |
and when ν = μ, the residue vanishes, so that we have to consider
| ΣΣ | c$_{λ,μ}$ | , |
| ΣΣ | a$^λ$ν (1 – e$^x$)$^λ$ | , |
and the residue of this is, by the first lemma,
| − ΣΣ | c$_{λ,μ}$ | , |
| − ΣΣ | a$^λ$ν | , |
which proves the lemma.
Take F(x) = 1/x$^n$ (1 – x$^a$) (1 – x$^b$) ... (1 – x$^l$) = ƒ(x)/x$^n$, since the sought number is its constant term.
Let ρ be a root of unity which makes ƒ(x) infinite when substituted for x. The function of which we have to take the residue is
| Σ ρ$^{−n}$e$^{nx}$ ƒ(ρe$^{−x}$) = Σ | ρ$^{−n}$e$^{nx}$ | . |
| Σ ρ$^{−n}$e$^{nx}$ ƒ(ρe$^{−x}$) = Σ | (1 – ρ$^a$e$^{−ax}$) (1 – ρ$^b$e$^{−bx}$) ... (1 – ρ$^l$e$^{−lx}$) | . |
We may divide the calculation up into sections by considering separately that portion of the summation which involves the primitive qth roots of unity, q being a divisor of one of the numbers a, b, ... l. Thus the qth wave is
| Σ | ρ$^{−n}$q e$^{nx}$ | , |
| Σ | (1 – ρ$^a$q e$^{−ax}$) (1 – ρ$^b$q e$^{−bx}$) ... (1 – ρ$^l$$_q$ e$^{−lx}$) | , |
which, putting 1/ρ$_q$ for ρ$_q$ and ν = 1/2(a + b + ... + l), may be written
| Σ | ρ$^ν$$_q$ e$^{νx}$ | , |
| Σ | (ρ$^{1/2a}$q e$^{1/2ax}$ – ρ$^{−1/2a}$q e$^{−1/2ax}$) (ρ$^{1/2b}$q e$^{1/2bx}$ – ρ$^{−1/2b}$q e$^{−1/2bx}$) ... (ρ$^{1/2l}$q e$^{1/2lx}$ – ρ$^{−1/2l}$q e$^{−1/2lx}$) | , |
and the calculation in simple cases is practicable.
Thus Sylvester finds for the coefficient of x$^n$ in
* 1
* 1 – x. 1 – x$^2$. 1 – x$^3$
the expression
| ν$^2$ | − | 7 | − | 1 | (−)ν + | 1 | (ρ$^ν$3 + ρ$^{−ν}$3), |
| 12 | − | 72 | − | 8 | (−)ν + | 9 | (ρ$^ν$3 + ρ$^{−ν}$3), |
where ν = n + 3.
Sylvester, Franklin, Durfee, G. S. Ely and others have evolved a constructive theory of partitions, the object of which is the contemplation of the partitions themselves, and the evolution of their properties from a study of their inherent characters. It is concerned Sylvester’s graphical method. for the most part with the partition of a number into parts drawn from the natural series of numbers 1, 2, 3 .... Any partition, say (521) of the number 8, is represented by nodes placed in order at the points of a rectangular lattice,
when the partition is given by the enumeration of the nodes by lines. If we enumerate by columns we obtain another partition of 8, viz. (321$^3$), which is termed the conjugate of the former. The fact or conjugacy was first pointed out by Norman Macleod Ferrers. If the original partition is one of a number n in i parts, of which the largest is j, the conjugate is one into j parts, of which the largest is i, and we obtain the theorem:— “The number of partitions of any number into i parts i parts or fewer, and having the largest part equal to j equal or less than j, remains the same when the numbers i and j are interchanged.”
The study of this representation on a lattice (termed by Sylvester the “graph”) yields many theorems similar to that just given, and, moreover, throws considerable light upon the expansion of algebraic series.
The theorem of reciprocity just established shows that the number of partitions of n into; parts or fewer, is the same as the number of ways of composing n with the integers 1, 2, 3, ... j. Hence we can expand 1/(1 – a. 1 – ax. 1 – ax$^2$. 1 – ax$^3$ ... ad inf. in ascending powers of a; for the coefficient of a$^j$x$^n$ in the expansion is the number of ways of composing n with j or fewer parts, and this we have seen in the coefficients of x$^n$ in the ascending expansion of 1/(1 – x. 1 – x$^2$ ... 1 – x$^j$. Therefore
| 1 | = 1 + | a | + | a$^2$ | + ... + | a$^j$ | + .... |
| 1 – a. 1 – ax. 1 – ax$^2$.... | = 1 + | 1 – x | + | 1 – x. 1 – x$^2$ | + ... + | 1 – x. 1 – x$^2$.... 1 – x$^j$ | + .... |
The coefficient of a$^j$x$^n$ in the expansion of
* 1
* 1 – a. 1 – ax. 1 – ax$^2$. ... 1 – ax$^i$
denotes the number of ways of composing n with j or fewer parts, none of which are greater than i. The expansion is known to be
| Σ | 1 – x$^{j+1}$. 1 – x$^{j+2}$. ... 1 – x$^{j+i}$ | a$^j$. |
| Σ | 1 – x. 1 – x$^2$. ... 1 – x$^i$ | a$^j$. |
It has been established by the constructive method by F. Franklin (Amer. Jour. of Math. v. 254), and shows that the generating function for the partitions in question is
| 1 – x$^{j+1}$. 1 – x$^{j+2}$. ... 1 – x$^{j+i}$ | , |
| 1 – x. 1 – x$^2$. ... 1 – x$^i$ | , |
which, observe, is unaltered by interchange of i and j.
Franklin has also similarly established the identity of Euler
| | $_{j=−∞}$ |
| (1 – x)(1 – x$^2$)(1 – x$^3$) ... ad inf. | = Σ (−) jx$^{1/2(3j2+j)}$, |
| | $^{j=+∞}$ |
known as the “pentagonal number theorem,” which on interpretation shows that the number of ways of partitioning n into an even number of unrepeated parts is equal to that into an uneven number, except when n has the pentagonal form 1/2(3j$^2$ + j), j positive or negative, when the difference between the numbers of the partitions is (−)$^j$.
To illustrate an important dissection of the graph we will consider those graphs which read the same by columns as by lines; these are called self-conjugate. Such a graph may be obviously dissected into a square, containing say θ$^2$ nodes, and into two graphs, one lateral and one subjacent, the latter being the conjugate of the former. The former graph is limited to contain not more than θ parts, but is subject to no other condition. Hence the number of self-conjugate partitions of n which are associated with a square of θ$^2$ nodes is clearly equal to the number of partitions of 1/2(n – θ$^2$) into θ or few parts, i.e. it is the coefficient of x$^{1/2(n−θ2)}$ in
| 1 | , |
| 1 – x. 1 – x$^2$.1 – x$^3$.... 1 – x$^θ$. | , |
and the whole generating function is
| 1 + $\sum _{\theta \ =\ 1}^{\theta \ =\ \infty }$ | x$^{θ2}$ | . |
| 1 + $\sum _{\theta \ =\ 1}^{\theta \ =\ \infty }$ | 1 – x$^2$. 1 – x$^4$. 1 – x$^6$. ... 1 – x$^{2θ}$ | . |
Now the graph is also composed of θ angles of nodes, each angle containing an uneven number of nodes; hence the partition is transformable into one containing θ unequal uneven numbers. In the case depicted this partition is (17, 9, 5, 1). Hence the number of the partitions based upon a square of θ$^2$ nodes is the coefficient of a$^θ$x$^n$ in the product (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... (1 + ax$^{2s+1}$) ..., and thence the coefficient of a$^θ$ in this product is x$^{θ2}$ / (1 – x$^2$. 1 – x$^4$. 1 – x$^6$ ... 1 – x$^{2θ}$), and we have the expansion
| (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... ad inf. = 1 + | x | a + | x$^4$ | a$^2$ + | x$^9$ | a$^3$ + ... |
| (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... ad inf. = 1 + | 1 – x$^2$ | a + | 1 – x$^2$. 1 – x$^4$ | a$^2$ + | 1 – x$^2$. 1 – x$^4$. 1 – x$^6$ | a$^3$ + ... |
Again, if we restrict the part magnitude to i, the largest angle of nodes contains at most 2i – 1 nodes, and based upon a square of θ$^2$ nodes we have partitions enumerated by the coefficient of a$^θ$x$^n$ in the product (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... (1 + ax$^{2i−1}$); moreover the same number enumerates the partition of 1/2(n – θ$^2$) into θ or fewer parts, of which the largest part is equal to or less than i – θ,
| 1 – x$^{i−θ+1}$. 1 – x$^{i−θ+2}$. 1 – x$^{i−θ+3}$. ... 1 – x$^i$ | , |
| 1 – x. 1 – x$^2$. 1 – x$^3$. ... 1 – x$^θ$ | , |
or of x$^n$ in
| 1 – x$^{2i−2θ+2}$. 1 – x$^{2i−2θ+4}$. ... 1 – x$^{2i}$ | xθ$^2$; |
| 1 – x$^2$. 1 – x$^4$. 1 – x$^6$. ... 1 – x$^{2θ}$ | xθ$^2$; |
hence the expansion
| (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... (1 + ax$^{2i−1}$) = 1 + Σθ=iθ=1 | 1 – x$^{2i−2θ+2}$. 1 – x$^{2i−2θ+4}$. ... 1 + x$^{2i}$ | x$^{θ2}$ a$^θ$. |
| (1 + ax) (1 + ax$^3$) (1 + ax$^5$) ... (1 + ax$^{2i−1}$) = 1 + Σθ=iθ=1 | 1 – x$^2$. 1 – x$^4$. 1 – x$^6$. ... 1 – x$^{2θ}$ | x$^{θ2}$ a$^θ$. |
There is no difficulty in extending the graphical method to three dimensions, and we have then a theory of a special kind of partition of multipartite numbers. Of such kind is theExtension to three dimensions. partition
/(a$_1$a$_2$a$_3$..., /(b$_1$b$_2$b$_3$..., /(c$_1$c$_2$c$_3$..., , /...)
of the multipartite number
/(a$_1$ + b$_1$ + c$_1$ + ..., a$_2$ + b$_2$ + c$_2$ + ..., a$_3$ + b$_3$ + c$_3$ + ..., ...)
if
a$_1$ ≥ a$_2$ ≥ a$_3$ ≥ ...; b$_1$ ≥ b$_2$ ≥ b$_3$ ≥ ..., ... a$_3$ ≥ b$_3$ ≥ c$_3$ ≥ ...,
for then the graphs of the parts $_{—————}$ a$_1$a$_2$a$_3$..., $_{—————}$ b$_1$b$_2$b$_3$..., ... are superposable, and we have what we may term a regular graph in three dimensions. Thus the partition (643, 632, 411) of the multipartite (16, 8, 6) leads to the graph
and every such graph is readable in six ways, the axis of z being perpendicular to the plane of the paper.
Ex. Gr.
| Plane parallel to | xy, | direction | Ox | reads | (643, 632, 411) |
| ”   ” | xy, | ” | Oy | ” | (333211, 332111, 311100) |
| ”   ” | yz, | ” | Oy | ” | (333, 331, 321, 211, 110, 110) |
| ”   ” | yz, | ” | Oz | ” | (333, 322, 321, 310, 200, 200) |
| ”   ” | zx, | ” | Oz | ” | (333322, 322100, 321000) |
| ”   ” | zx, | ” | Ox | ” | (664, 431, 321) |
the partitions having reference to the multipartite numbers 16, 8, 6, 976422, 13, 11, 6, which are brought into relation through the medium of the graph. The graph in question is more conveniently represented by a numbered diagram, viz.—
| 3 | 3 | 3 | 3 | 2 | 2 |
| 3 | 2 | 2 | 1 | | |
| 3 | 2 | 1 | | | |
and then we may evidently regard it as a unipartite partition on the points of a lattice,
the descending order of magnitude of part being maintained along every line of route which proceeds from the origin in the positive directions of the axes.
This brings in view the modern notion of a partition, which has enormously enlarged the scope of the theory. We consider any number of points in plano or in solido connected (or not) by lines in pairs in any desired manner and fix upon any condition, such as is implied by the symbols ≥, >, =, <, ≤, ≷, as affecting any pair of points so connected. Thus in ordinary unipartite partition we have to solve in integers such a system as
α$_1$ + α$_2$ + α$_3$ + ... + α$_n$ = n,
the points being in a straight line. In the simplest example of the three-dimensional graph we have to solve the system
| α$_1$ ≥ α$_2$ | |
| ≚ ≙ | α$_1$ + α$_2$ + α$_3$ + α$_4$ = n, |
| α$_3$ ≥ α$_4$ | |
and a system for the general lattice constructed upon the same principle. The system has been discussed by MacMahon, Phil. Trans. vol. clxxxvii. A, 1896, pp. 619-673, with the conclusion that if the numbers of nodes along the axes of x, y, z be limited not to exceed the numbers m, n, l respectively, then writing for brevity 1 – x$^s$ = (s), the generating function is given by the product of the factors
| | | | | | x |
| | (l + 1) | . | (l + 2) | . . . . | (l + m) |
| | (1) | . | (2) | . . . . | (m) |
| | (l + 2) | . | (l + 3) | . . . . | (l + m + 1) |
| | (2) | . | (3) | . . . . | (m + 1) |
| | (l + n) | . | (l + n + 1) | . . . . | (l + m + n – 1) |
| | (n) | . | (n + 1) | . . . . | (m + n – 1) |
| y | | | | |
one factor appearing at each point of the lattice.
In general, partition problems present themselves which depend upon the solution of a number of simultaneous relations in integers of the form
the coefficients λ being given positive or negative integers, and in some cases the generating function has been determined in a form which exhibits the fundamental solutions of the problems from which all other solutions are derivable by addition. (See MacMahon, Phil. Trans. vol. cxcii. (1899), pp. 351-401; and Trans. Camb. Phil. Soc. vol. xviii. (1899), pp. 12-34.)
The number of distributions of n objects (p$_1$p$_2$p$_3$ ...) into parcels (m) is the coefficient of b$^m$(p$_1$p$_2$p$_3$ ...)x$^n$ in the development of the Method of symmetric functions.fraction
1 :
| | (1 − bαx. 1 − bβx. 1 − bγx ... | ) |
| × | (1 − bα$^2$x$^2$. 1 − bαβx$^2$. 1 − bβ$^2$x$^2$ ... | ) |
| × | (1 − bα$^3$x$^3$. 1 − bα$^2$βx$^3$. 1 − bαβγx$^3$ ... | ) |
and if we write the expansion of that portion which involves products of the letters α, β, γ, . . . of degree r in the form
we may write the development
| $_{r=∞}$ | |
| Π | (1 + h$_{r1}$ bx$^r$ + h$_{r2}$ b$^2$x$^{2r}$ + ...), |
| $^{r=1}$ |
and picking out the coefficient of b$^m$ x$^n$ we find
t$_1$ t$_2$ t$_3$
The quantities h are symmetric functions of the quantities α, β, γ, . . . which in simple cases can be calculated without difficulty, and then the distribution function can be formed.
Ex. Gr.—Required the enumeration of the partitions of all multipartite numbers (p$_1$p$_2$p$_3$ ...) into exactly two parts. We find
* h$_{22}$ = h$_4$ − h$_3$h$_1$ + h$^2$2
* h$_{32}$ = h$_6$ − h$_5$h$_1$ + h$_4$h$_2$
* h$_{42}$ = h$_8$ − h$_7$h$_1$ + h$_6$h$_2$ + h$_5$h$_3$ + h$^2$4,
and paying attention to the fact that in the expression of h$_{r2}$ the term h2 r is absent when r is uneven, the law is clear. The generating function is
h$_2$x$^2$ + h$_2$h$_1$x$^3$ + (h$_4$ + h$^2$2)x$^4$ + (h$_4$h$_1$ + h$_3$h$_2$)x$^5$ + (h$_6$ + 2h$_4$h$_2$)x$^6$ + (h$_6$h$_1$ + h$_5$h$_2$ + h$_4$h$_3$)x$^7$ + (h$_8$ + 2h$_6$h$_2$ + h$^2$4)x$^8$ + ...
Taking
the term 5(21$^2$) indicates that objects such as a, a, b, c can be partitioned in five ways into two parts. These are a | a, b, c; b | a; a, c; c | a, a, b; a, a | b, c; a, b | a, c. The function h$_{rs}$ has been studied. (See MacMahon, Proc. Lond. Math. Soc. vol. xix.) Putting x equal to unity, the function may be written (h$_2$ + h$_4$ + h$_6$ + ...) (1 + h$_1$ + h$_2$ + h$_3$ + h$_4$ + ...), a convenient formula.
The method of differential operators, of wide application to problems of combinatorial analysis, has for its leading idea the designing of a function and of a differential operator, so that when the operator is performed upon the function a number is reached which enumerates the solutions Method of differential operators. of the given problem. Generally speaking, the problems considered are such as are connected with lattices, or as it is possible to connect with lattices.
To take the simplest possible example, consider the problem of finding the number of permutations of n different letters. The ​function is here x$^n$, and the operator (d/dx)$^n$ = δ$^n$ x , yielding δ$^n$ x x$^n$ = n! the number which enumerates the permutations. In fact—
δ$_x$x$^n$ = δ$_x$ . x . x . x . x . x . x . ...,
and differentiating we obtain a sum of n terms by striking out an x from the product in all possible ways. Fixing upon any one of these terms, say x . x . x . x . ..., we again operate with δ$_x$ by striking out an x in all possible ways, and one of the terms so reached is x . x . x . x . x . .... Fixing upon this term, and again operating and continuing the process, we finally arrive at one solution of the problem, which (taking say n = 4) may be said to be in correspondence with the operator diagram—
the number in each row of compartments denoting an operation of δ$_x$. Hence the permutation problem is equivalent to that of placing n units in the compartments of a square lattice of order n in such manner that each row and each column contains a single unit. Observe that the method not only enumerates, but also gives a process by which each solution is actually formed. The same problem is that of placing n rooks upon a chess-board of n$^2$ compartments, so that no rook can be captured by any other rook.
Regarding these elementary remarks as introductory, we proceed to give some typical examples of the method. Take a lattice of m columns and n rows, and consider the problem of placing units in the compartments in such wise that the sth column shall contain λ$_s$ units (s = 1, 2, 3, ... m), and the tth row p$_t$ units (t = 1, 2, 3, ... n).
Writing
and D$_p$ = 1/p! (δ$_{α1}$ + α$_1$δ$_{α2}$ + α$_2$δ$_{α3}$ + ...)$^p$, the multiplication being symbolic, so that D$_p$ is an operator of order p, the function is
and the operator D$_{p1}$D$_{p2}$D$_{p3}$ ... D$_{pn}$. The number D$_{p1}$D$_{p2}$ ... D$_{pn}$a$_{λ1}$a$_{λ2}$a$_{λ3}$ ... a$_{λm}$ enumerates the solutions. For the mode of operation of D$_p$ upon a product reference must be made to the section on “Differential Operators” in the article Algebraic Forms. Writing
... ΑΣα$^{p1}$1 α$^{p2}$2 ... α$^{pn}$n + ...,
or, in partition notation,
... + Α(p$_1$p$_2$ ... p$_n$) ... + D$_{p1}$D$_{p2}$ ... D$_{pn}$ (1$^{λ1}$) (1$^{λ2}$) ... (1$^{λm}$) = Α
and the law by which the operation is performed upon the product shows that the solutions of the given problem are enumerated by the number A, and that the process of operation actually represents each solution.
Ex. Gr.—Take
* λ$_1$ = 3, λ$_2$ = 2, λ$_3$ = 1,
* p$_1$ = 2, p$_2$ = 2, p$_3$ = 1, p$_4$ = 1,
* D$^2$2D$^2$1 a$_3$a$_2$a$_1$ = 8,
and the process yields the eight diagrams:—
viz. every solution of the problem. Observe that transposition of the diagrams furnishes a proof of the simplest of the laws of symmetry in the theory of symmetric functions.
For the next example we have a similar problem, but no restriction is placed upon the magnitude of the numbers which may appear in the compartments. The function is now h$_{λ1}$h$_{λ2}$ ... h$_{λm}$, h$_{λm}$ being the homogeneous product sum of the quantities a, of order λ. The operator is as before
D$_{p1}$D$_{p2}$ ... D$_{pm}$,
and the solutions are enumerated by
h$_{λ1}$h$_{λ2}$ ... h$_{λm}$.
Putting as before λ$_1$ = 3, λ$_2$ = 2, λ$_3$ = 1, p$_1$ = 2, p$_2$ = 2, p$_3$ = 1, p$_4$ = 1, the reader will have no difficulty in constructing the diagrams of the eighteen solutions.
The next and last example of a multitude that might be given shows the extraordinary power of the method by solving the famous problem of the “Latin Square,” which for hundreds of years had proved beyond the powers of mathematicians. The problem consists in placing n letters a, b, c, ... n in the compartments of a square lattice of n$^2$ compartments, no compartment being empty, so that no letter occurs twice either in the same row or in the same column. The function is here
α$^2$n−1 α$_n$)$^n$,
and the operator D$^n$2$^n$−1, the enumeration being given by
(Σα$^{2n−1}$1 α$^{2n−2}$ ... α$^2$n−1 α$_n$)$^n$.
See Trans. Camb. Phil. Soc. vol. xvi. pt. iv. pp. 262-290.
Authorities.—P. A. MacMahon, “Combinatory Analysis: A Review of the Present State of Knowledge,” Proc. Lond. Math. Soc. vol. xxviii. (London, 1897). Here will be found a bibliography of the Theory of Partitions. Whitworth, Choice and Chance; Édouard Lucas, Théorie des nombres (Paris, 1891); Arthur Cayley, Collected Mathematical Papers (Cambridge, 1898), ii. 419; iii. 36, 37; iv. 166-170; v. 62-65, 617; vii. 575; ix. 480-483; x. 16, 38, 611; xi. 61, 62, 357-364, 589-591; xii. 217-219, 273-274; xiii. 47, 93-113, 269; Sylvester, Amer. Jour, of Math. v. 119 251; MacMahon, Proc. Lond. Math. Soc. xix. 228 et seq.; Phil. Trans. clxxxiv. 835-901; clxxxv. 111-160; clxxxvii. 619-673; cxcii. 351-401; Trans. Camb. Phil. Soc. xvi. 262-290. (P. A. M.)