denoted by the partition
(sσ_{1}
1 sσ_{2}
2 sσ_{3}
3...).
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
(sσ_{1}
1 sσ_{2}
2 sσ_{3}
3...).
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
(sσ_{1}
1 sσ_{2}
2 sσ_{3}
3...).
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
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} ... + ...
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}! ... |
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}! ... |
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π11 pπ22 pπ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 12 we bring this to the still more convenient form
12 | 1 | . |
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 12 11 − 2a = 12 + Σ F(p)α^{p}, and thence F(p) = 2^{p − 1}. Again 12 · 11 − 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)! | − ... |
0! p_{1}! p_{2}! | 1! (p_{1} − 1)! (p_{2} − 1)! | 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
12 · | 1 | . |
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
12 · | 1 | , |
{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
12 · | 1 | , |
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
12 (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 12 Σ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 | , | |
12 · | {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
The theory
of permu-
tations.
a comprehensive theory of Permutations, which it is convenient to discuss shortly here.
If X_{1}, X_{2}, X_{3}, ... X_{n} be linear functions given by the matricular relation
(X_{1}, X_{2}, X_{3}, ... X_{n}) = | (a_{11} | a_{12} | ... | a_{1n}) | (x_{1}, x_{2}, ... x_{n}) |
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}|
s_{1}s_{2} ... s_{n}x_{1}x_{2} ... x_{n},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