Page:EB1911 - Volume 06.djvu/776

denoted by the partition ${\big (}s_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}.$ Employing a more general notation we may write

Xπ₁
p₁ Xπ₂
p₂ Xπ₃
p₃ ... = ΣPxσ₁
s₁ xσ₂
s₂ xσ₃
s₃ ...

and then P is the distribution function of objects into parcels (pπ₁
1⁠ pπ₂
2⁠ pπ₃
3⁠ ...), the distributions being such as to have the specification ${\big (}s_{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π₁
p₁ Xπ₂
p₂ Xπ₃
p₃ ... = ΣΣθ (λl₁
1⁠ λl₂
2⁠ λl₃
3⁠ ...) xσ₁
s₁ xσ₂
s₂ xσ₃
s₃ ...

indicating that for distributions of specification ${\big (}s_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}.$. there are θ ways of distributing n objects denoted by (λl₁
1⁠ λl₂
2⁠ λl₃
3⁠ ...) amongst n parcels denoted by (p^π1₁ p^π2₂ p^π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

Xπ₁
p₁ Xπ₂
p₂ Xπ₃
p₃ ... ... = ... + θ (λl₁
1⁠ λl₂
2⁠ λl₃
3⁠ ...) xσ₁
s₁ xσ₂
s₂ xσ₃
s₃ ... + ...

then also

X^l1_λ1 X^l2_λ2 X^l3_λ3 ... = ... + θ (p^π1₁ p^π2₂ p^π3₃ ...) xσ₁
s₁ xσ₂
s₂ xσ₃
s₃ ... + ...

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 (π₁ π₂ π₃) be a partition of m.     

(pπ₁
1  pπ₂
2 pπ₃
3 ...) a partition of n.

Of the whole number of distributions of the n objects, there will be a certain number such that n₁ parcels each contain p₁ objects, and in general π_s parcels each contain p_s objects, where s = 1, 2, 3, ... Consider the product hπ₁
p₁ hπ₂
p₂ hπ₃
p₃ ... which can be permuted in m!/π₁!π₂!π₃! ... ways. For each of these ways hπ₁
p₁ hπ₂
p₂ hπ₃
p₃ ... 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 xⁿ in (h₁x + h₂x² + h₃x³ + ... )^m. The value of A_{(p^π11 p^π22 p^π33 ...), (1^m)} is the coefficient of (p^π₁1 p^π₂2 p^π₃3 ...)xⁿ 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 p₁ = p₂ = p₃ = ... = π₁ = π₂ = π₃ ... = 1 this expression reduces to the mth divided differences of 0ⁿ. The expression gives the compositions of the multipartite number p^π1₁ p^π2₂ p^π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₁ + h₂ + h₃ + .../ 1 − h₁ − h₂ − h₃ + ... which may be given the form a₁ − a₂ + a₃ − .../1 − 2(a₁ − a₂ + a₃ − ...). Adding 1/2 we bring this to the still more convenient form

1/2	1	.
	1 − 2(a1 − a2 + a3 − ...)

Let F (p^π1₁ p^π2₂ p^π3₃ ... ) denote the total number of compositions of the multipartite p^π1₁ p^π2₂ p^π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₁p₂) α^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 p₁p₂p₃ ... p_s (p₁p₂p₃ ... p_s) or of the single term αp₁
1  αp₂
2  αp₃
3  ... αp_s
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

t₁α₁, t₂α₂, t₃α₃, ... t_sα_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 t₁, t₂, &c., are put equal to unity, is equal to the coefficient of the same term in the product

1/2 (2α₁ + α₂ + ... + α_s)^p₁ (2α₁ + 2α₂ + ... + α_s)^p₂ ... (2α₁ + 2α₂ + ... + 2α_s)^p_s.

This result gives a direct connexion between the number of compositions and the permutations of the letters in the product αp₁
1  αp₂
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₁ = p₁ this may be written

2p₁⁻¹ Σ2^{q1+q2+ ... +qs}.

Ex. Gr.—For the bipartite 22, p₁ = p₂ = 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 (2² + 2 + 2 + 2 + 2 + 2⁰) = 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

(t₁α₁)^p₁ (t₂α₂)^p₂ ... (t_sα_s)^p_s.

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₁, X₂, X₃, ... X_n 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 s₁x₁, s₂x₂, s₃x₃, ... s_nx_n only is

1

|(1 − a₁₁s₁x₁) (1 − a₂₂s₂x₂) (1 − a₃₃s₃x₃) ... (1 − a_nns_nx_n)|

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

1 − Σ |a₁₁|s₁x₁ + Σ |a₁₁a₂₂|s₁s₂x₁x₂ − ... + (–)ⁿ |a₁₁a₂₂a₃₃ ... a_nn|

s₁s₂ ... s_nx₁x₂ ... x_n,

where |a₁₁|, |a₁₁a₂₂|, ... |a₁₁a₂₂, ... a_nn| denote the several co-axial minors of the determinant

|a₁₁a₂₂ ... a_nn|

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⁠ xξ₂
2⁠ xξ_n
n⁠