in the product
(a11x1 + a12x2 + ... + a1nxn)ξ1 (a21x1 + a22x2 + ... + a2nxn)ξ2 ... (an1x1 + an2x2 + ... + annxn)ξn
is equal to the coefficient of the same term in the expansion ascending-wise of the fraction
11 − Σ |a11|x1 + Σ |a11a22|x1x2 + (–)n |a11a22 ... | x1x2 ... xn.
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.
(x1 + x2 + ... − xn)ξ1+ξ2+ . . . +ξn
and
| 1 | . |
| 1 − (x1 + x2 + ... + xn) |
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 xs is in a position originally occupied by an x3 for all
values of s. This is a generalization of the “Problème des rencontres”
or of “derangements.” We have merely to put
a11 = a22 = a33 = ... = ann = 0
and the remaining elements equal to unity. The generating product is
(x1 + x3 + ... + xn)ξ2 ... (x1 + x2 + ... + xn−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 − Σ x1x2 − 2Σ x1x2x3 − ... − sΣ x1x2 ... xs+1 − ... − (n − 1) x1x2 ... xn |
or writing
(x − x1) (x − x2) ... (x − xn) = xn − a1xn−1 + a2xn−2 − ...,
this is
| 1 |
| 1 − a2 − 2a3 − 3a4 − ... − (n − 1) an |
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
(ax1 + x2 + ... + xn)ξ1 (x1 + ax2 + ... + xn)ξ2 ... (x1 + x2 + ... + axn)ξn
in which the sought number is the coefficient of am xξ11 xξ22 ... xξnn. 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Σ x1 + (a − 1) (a + 1)Σ x1x2 − ... + (−)n (a − 1)n−1 (a + n − 1)x1x2 ... xn. |
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 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
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 ζpxn in the ascending expansion of the fraction
| 1 | , |
| 1 − ζxa. 1 − ζxb. 1 − ζxc. ... |
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
| 1 − ζkxka | · | 1 − ζkxkb | · | 1 − ζkxkc | · ... |
| 1 − ζxa | 1 − ζxb | 1 − ζxc |
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 − xa. 1 − xb. 1 − xc. ... |
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 |
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
| 1 |
| (1 − xaybzc ...) (1 − xa′yb′zc′ ...) (1 − xa″yb″zc″ ...) ... |
which enumerates the partitions of the multipartite number nn′n″ ... into the parts
Sylvester has determined an analytical expression for the coefficient of xn in the expansion of
| 1 | . |
| (1 − xa) (1 − xb) ... (1 − xi) |
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
| (1 − ex)−i−1 = (1 − ex)−i + ex(1 − ex)−i−1 = (1 − ex)−i + | d | (1 − ex)−i · | 1 | . |
| dx | i |
Here the residue of ddx (1 − ex)−i · 1i is zero, and therefore the residue of (1 − ex)−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λ, μ | + Σ | γλ | . |
| (aμ − x)λ | xλ |
