Open main menu
This page has been proofread, but needs to be validated.
754
COMBINATORIAL ANALYSIS

denoted by the partition (sσ1
1
sσ2
2
sσ3
3
...). Employing a more general notation we may write

Xπ1
p1
Xπ2
p2
Xπ3
p3
... = ΣPxσ1
s1
xσ2
s2
xσ3
s3
...

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
p1
Xπ2
p2
Xπ3
p3
... = ΣΣθ (λl1
1
λl2
2
λl3
3
...) xσ1
s1
xσ2
s2
xσ3
s3
...

indicating that for distributions of specification (sσ1
1
sσ2
2
sσ3
3
...). there are θ ways of distributing n objects denoted by (λl1
1
λl2
2
λl3
3
...) amongst n parcels denoted by (pπ11 pπ22 pπ33 ...), 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

Xπ1
p1
Xπ2
p2
Xπ3
p3
... ... = ... + θ (λl1
1
λl2
2
λl3
3
...) xσ1
s1
xσ2
s2
xσ3
s3
... + ...

then also

Xl1λ1 Xl2λ2 Xl3λ3 ... = ... + θ (pπ11 pπ22 pπ33 ...) xσ1
s1
xσ2
s2
xσ3
s3
... + ...

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 (Im).—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 n1 parcels each contain p1 objects, and in general πs parcels each contain ps objects, where s = 1, 2, 3, ... Consider the product hπ1
p1
hπ2
p2
hπ3
p3
... which can be permuted in m!/π1!π2!π3! ... ways. For each of these ways hπ1
p1
hπ2
p2
hπ3
p3
... will be a distribution function for distributions of the specified type. Hence, regarding all the permutations, the distribution function is

m! hπ1
p1
hπ2
p2
hπ3
p3
...
π1!π2!π3! ...

and regarding, as well, all the partitions of n into exactly m parts, the desired distribution function is

Σ m! hπ1
p1
hπ2
p2
hπ3
p3
...   [Σπ = m, Σπp = n],
π1!π2!π3! ...

that is, it is the coefficient of xn in (h1x + h2x² + h3x³ + ... )m. The value of A(pπ11 pπ22 pπ33 ...), (1m) is the coefficient of (pπ11 pπ22 pπ33 ...)xn in the development of the above expression, and is easily shown to have the value

        ( p1 + m − 1 ) π1 ( p2 + m − 1 ) π2 ( p3 + m − 1 ) π3 ...
  p1   p2   p3  
( m ) ( p1 + m − 2 ) π1 ( p2 + m − 2 ) π2 ( p3 + m − 2 ) π3 ...
1 p1   p2   p3  
+ ( m ) ( p1 + m − 3 ) π1 ( p2 + m − 3 ) π2 ( p3 + m − 3 ) π3 ...
2 p1   p2   p3  
− ... to m terms.

Observe that when p1 = p2 = p3 = ... = π1 = π2 = π3 ... = 1 this expression reduces to the mth divided differences of 0n. The expression gives the compositions of the multipartite number pπ11 pπ22 pπ33 ... 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 h1 + h2 + h3 + .../ 1 − h1h2h3 + ... which may be given the form a1a2 + a3 − .../1 − 2(a1a2 + a3 − ...). Adding 1/2 we bring this to the still more convenient form

1/2 1 .
1 − 2(a1a2 + a3 − ...)

Let F (pπ11 pπ22 pπ33 ... ) denote the total number of compositions of the multipartite pπ11 pπ22 pπ33 .... Then 1/2 1/1 − 2a = 1/2 + Σ F(p)αp, and thence F(p) = 2p − 1. Again 1/2 · 1/1 − 2(α + β − αβ) = Σ F(p1p2) αp1βp2, and expanding the left-hand side we easily find

F(p1p2) = 2p1 + p2 − 1 (p1 + p2)! − 2p1 + p2 − 2 (p1 + p2 − 1)! + 2p1 + p2 − 3 (p1 + p2 − 2)! − ...
0! p1! p2! 1! (p1 − 1)! (p2 − 1)! 2! (p1 − 2)! (p2 − 2)!

We have found that the number of compositions of the multipartite p1p2p3 ... ps (p1p2p3 ... ps) or of the single term αp1
αp2
αp3
... αps
s 
in the development according to ascending powers of the algebraic fraction

1/2 · 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

1/2 · 1 ,
{1 − t1 (2α1 + α2 + ... + αs)} {1 − t2 (2α1 + 2α2 + ... + αs)} ... {1 − ts (2α1 + 2α2 + ... + 2αs)}

which is composed entirely of powers of

t1α1, t2α2, t3α3, ... tsαs

has the expression

1/2 · 1 ,
1 − 2 (Σt1α1 − Σt1t2α1α2 + Σt1t2t3α1α2α3 − ... + (−)s + 1t1t2 ... tsα1α2 ... αs)

and therefore the coefficient of αp11 αp22 ... αpss  in the latter fraction, when t1, t2, &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 αp1
αp2
... αps
s 
. Selecting any permutation, suppose that the letter ar occurs qr times in the last pr + pr+1 + ... + ps places of the permutation; the coefficient in question may be represented by 1/2 Σ2q1+q2+ ... +qs, the summation being for every permutation, and since q1 = p1 this may be written

2p1−1 Σ2q1+q2+ ... +qs.

Ex. Gr.—For the bipartite 22, p1 = p2 = 2, and we have the following scheme:—

α1 α1 α2 α2 q2 = 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 (22 + 2 + 2 + 2 + 2 + 20) = 26.

We may regard the fraction

1 ,
1/2 · {1 − t1 (2α1 + α2 + ... + αs)} {1 − t2 (2α1 + 2α2 + ... + αs)} ... {1 − ts (2α1 + 2α2 + ... + 2αs)}

as a redundant generating function, the enumeration of the compositions being given by the coefficient of

(t1α1)p1 (t2α2)p2 ... (tsα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 X1, X2, X3, ... Xn be linear functions given by the matricular relation

(X1, X2, X3, ... Xn) = (a11 a12 ... a1n) (x1, x2, ... xn)
  a21 a22 ... a2n  
  . . ... .  
  . . ... .  
  an1 an2 ... ann  

that portion of the algebraic fraction,

1 ,
(1 − s1X1) (1 − s2X2) ... (1 − snXn)

which is a function of the products s1x1, s2x2, s3x3, ... snxn only is

1
|(1 − a11s1x1) (1 − a22s2x2) (1 − a33s3x3) ... (1 − annsnxn)|

where the denominator is in a symbolic form and denotes on expansion

1 − Σ |a11|s1x1 + Σ |a11a22|s1s2x1x2 − ... + (–)n |a11a22a33 ... ann|

s1s2 ... snx1x2 ... xn,

where |a11|, |a11a22|, ... |a11a22, ... ann| denote the several co-axial minors of the determinant

|a11a22 ... ann|

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