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
or writing
(x - x1) (x - x2) ... (x - xn) = xn- a1xn-1+ a2xn-2- ...,
this is
Again, consider the general problem of “derangements.” We have to find the number of permutations such that exactlymof the letters are in places they originally occupied. We have the particular redundant product
(ax1+ x2+ ... + xn)ξ1(x1+ ax2+ ... + xn)ξ2... (x1+ x2+ ... + axn)ξn
in which the sought number is the coefficient of amxξ11xξ22... xξnn. The true generating function is derived from the determinant
and has the form
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 x1, x2, ... x1x2... in the denominator of the real generating function must satisfy 2n- 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 theCase III.number n. It is usual to arrange the numbers comprised in the 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
xa× xb× xc× ... xa+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 ζpxnin the ascending expansion of the fraction
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 + ζxa) (1 + ζxb) (1 + ζxc) ...;
if each part may occur at most twice,
(1 + ζxa+ ζ2x2a) (1 + ζxb+ ζ2x2b) (1 + ζxc+ ζ2x2c) ...;
and generally if each part may occur at most k - 1 times it is
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
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 + ... = na′x + b′y + c′z + ... = n′a″x + b″y + c″z + ... = n″
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 xnyn′zn″... in the expansion of the fraction
which enumerates the partitions of the multipartite numbernn′n″ ...into the parts
abc ...,a′b′c′ ...,a″b″c″ .......
Sylvester has determined an analytical expression for the coefficient of xnin the expansion of
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 - ex)-i, is -1. For when i is unity, it is obviously the case, and
Here the residue of d/dx (1 - ex)-i· 1/i is zero, and therefore the residue of (1 - ex)-iis 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
The constant term is
Let aνbe a value of x which makes the fraction infinite. The residue of
is equal to the residue of
and when ν = μ, the residue vanishes, so that we have to consider
and the residue of this is, by the first lemma,
which proves the lemma.
Take F(x) = 1 / [xn(1 - xa) (1 - xb) ... (1 - xl)] = ∫(x) / xn, 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
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 qthwaveis
which, putting 1 / ρqfor ρqand ν = ½(a + b + ... + l), may be written
and the calculation in simple cases is practicable.
Thus Sylvester finds for the coefficient of xnin
the expression
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 aSylvester’s graphical method.study of their inherent characters. It is concerned 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³), 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². 1 - ax³ ... ad inf.) in ascending powers of a; for the coefficient of ajxnin the expansion is the number of ways of composing n with j or fewer parts, and this we have seen in the coefficients of xnin the ascending expansion of 1 / (1 - x. 1 - x² ... 1 - xj). Therefore
The coefficient of ajxnin the expansion of
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
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
which, observe, is unaltered by interchange of i and j.
Franklin has also similarly established the identity of Euler
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 ½(3j² + 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 θ² 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 θ² nodes is clearly equal to the number of partitions of ½(n - θ² into θ or few parts,i.e.it is the coefficient of x½(n-θ²)in
or of xnin
and the whole generating function is
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 θ² nodes is the coefficient of aθxnin the product (1 + ax) (1 + ax3) (1 + ax5) ... (1 + ax2s+1) ..., and thence the coefficient of aθin this product is xθ2/ (1 - x2. 1 - x4. 1 - x6... 1 - x2θ), and we have the expansion
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 θ² nodes we have partitions enumerated by the coefficient of aθxnin the product (1 + ax) (1 + ax3) (1 + ax5) ... (1 + ax2i-1); moreover the same number enumerates the partition of ½(n - θ²) into θ or fewer parts, of which the largest part is equal to or less than i - θ, and is thus given by the coefficient of x½(n-θ²)in the expansion of
or of xnin
hence the expansion
There is no difficulty in extending the graphical method to threeExtension to three dimensions.dimensions, and we have then a theory of a special kind of partition of multipartite numbers. Of such kind is the partition
(a1a2a3...,(b1b2b3...,(c1c2c3..., ...)
of the multipartite number
(a1+ b1+ c1+ ..., a2+ b2+ c2+ ..., a3+ b3+ c3+ ..., ...)
if
a1≥ a2≥ a3≥ ...; b1≥ b2≥ b3≥ ..., ...a3≥ b3≥ c3≥ ...,
for then the graphs of the partsa1a2a3...,b1b2b3..., ... are superposable, and we have what we may term aregulargraph 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.
the partitions having reference to the multipartite numbers16, 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.—
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 alongeveryline 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 pointsin planoorin solidoconnected (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α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
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 - xs= (s), the generating function is given by the product of the factors
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
λ1α1+ λ2α2+ λ3α3+ ... ≥ 0,
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; andTrans. Camb.Phil. Soc.vol. xviii. (1899), pp. 12-34.)
The number of distributions of n objects (p1p2p3...) into parcelsMethod of symmetric functions.(m) is the coefficient of bm(p1p2p3...)xnin the development of the fraction
and if we write the expansion of that portion which involves products of the letters α, β, γ, ... of degree r in the form
1 + hr1bxr+ hr2b2x2r+ ... ,
we may write the development
Πr = ∞r = 1(1 + hr1bxr+ hr2b2x2r+ ...),
and picking out the coefficient of bmxnwe find
Σ hτ1hτ2hτ3... ,t1t2t3
where
Σ τ = m, Σ rt = n.
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 (p1p2p3...) into exactly two parts. We find
h2²= h4- h3h1+ h²2h3²= h6- h5h1+ h4h2h4²= h8- h7h1+ h6h2+ h5h3+ h²4,
h2²= h4- h3h1+ h²2
h3²= h6- h5h1+ h4h2
h4²= h8- h7h1+ h6h2+ h5h3+ h²4,
and paying attention to the fact that in the expression of hr2the term h²ris absent when r is uneven, the law is clear. The generating function is
h2x2+ h2h1x3+ (h4+ h22)x4+ (h4h1+ h3h2)x5+ (h6+ 2h4h2)x6+ (h6h1+ h5h2+ h4h3)x7+ (h8+ 2h6h2+ h24)x8+ ...
Taking
h4+ h22= h4+ {(2) + (12)}2= 2(4) + 3(31) + 4(22) + 5(212) + 7(14),
the term 5(21²) 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 hrshas been studied. (See MacMahon,Proc. Lond. Math. Soc.vol. xix.) Putting x equal to unity, the function may be written (h2+ h4+ h6+ ...) (1 + h1+ h2+ h3+ h4+ ...), 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,Method of differential operators.so that when the operator is performed upon the function a number is reached which enumerates the solutions 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. Thefunction is here xn, and the operator (d/dx)n= δnx, yielding δnxxn= n! the number which enumerates the permutations. In fact—
δxxn= δ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 δxby 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 cempartments 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² 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 λsunits (s = 1, 2, 3, ... m), and the tth row p1units (t = l, 2, 3, ... n).
Writing
1 + a1x + a2x² + ... + ... = (1 + a1x) (1 + a2x)(1 + a3x) ...
and Dp= 1/p! (δα1+ α1δα2+ α2δα3+ ...)p, the multiplication being symbolic, so that Dpis an operator of order p, the function is
aλ1aλ2aλ3... aλm,
and the operator Dp1Dp2Dp3... Dpn. The number Dp1Dp2... Dpnaλ1aλ2aλ3... aλmenumerates the solutions. For the mode of operation of Dpupon a product reference must be made to the section on “Differential Operators” in the articleAlgebraic Forms. Writing
aλ1aλ2... aλm= ... ΑΣ αp11αp22... αpnn+ ...,
or, in partition notation,
(1λ1) (1λ2) ... (1λm) = ... + Α(p1p2... pn) ... + Dp1Dp2... Dpn(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,p1= 2, p2= 2, p3= 1, p4= 1,D²2D²1a3a2a1= 8,
λ1= 3, λ2= 2, λ3= 1,
p1= 2, p2= 2, p3= 1, p4= 1,
D²2D²1a3a2a1= 8,
and the process yields the eight diagrams:—