Page:EB1911 - Volume 06.djvu/778

This page has been proofread, but needs to be validated.

756

COMBINATORIAL ANALYSIS

The constant term is

ΣΣ	c_{λ, μ}	,
	a^λν

Let a_ν be a value of x which makes the fraction infinite. The residue of

ΣΣΣ	c_{λ, μ}	+ Σ	γ_λ
	(a_μ – a_νe^x)^λ		a^λν e^λx

is equal to the residue of

ΣΣΣ	c_{λ, μ}	,
	(a_μ – a_νe^x)^λ

and when ν = μ, the residue vanishes, so that we have to consider

ΣΣ	c_{λ, μ}	,
	a^λν (1 – e^x)^λ

and the residue of this is, by the first lemma,

− ΣΣ	c_{λ, μ}	,
	a^λν

which proves the lemma.

Take F(x) = 1/xⁿ (1 – x^a) (1 – x^b) ... (1 – x^l) = ƒ(x)/xⁿ, 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

Σ ρ⁻ⁿe^nx ƒ(ρe^−x) = Σ	ρ⁻ⁿe^nx	.
	(1 – ρ^ae^−ax) (1 – ρ^be^−bx) ... (1 – ρ^le^−lx)

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 qth wave is

Σ	ρ⁻ⁿq e^nx	,
	(1 – ρ^aq e^−ax) (1 – ρ^bq e^−bx) ... (1 – ρ^l_q e^−lx)

which, putting 1/ρ_q for ρ_q and ν = 1/2(a + b + ... + l), may be written

Σ	ρ^ν_q e^νx	,
	(ρ^1/2aq e^1/2ax – ρ^−1/2aq e^−1/2ax) (ρ^1/2bq e^1/2bx – ρ^−1/2bq e^−1/2bx) ... (ρ^1/2lq e^1/2lx – ρ^−1/2lq e^−1/2lx)

and the calculation in simple cases is practicable.

Thus Sylvester finds for the coefficient of xⁿ in

1

1 – x. 1 – x². 1 – x³

the expression

ν²	−	7	−	1	(−)ν +	1	(ρ^ν3 + ρ^−ν3),
12		72		8		9

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 a study of their inherent characters. It is concerned Sylvester’s graphical method. 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 a^jxⁿ in the expansion is the number of ways of composing n with j or fewer parts, and this we have seen in the coefficients of xⁿ in the ascending expansion of 1/(1 – x. 1 – x² ... 1 – x^j. Therefore

1	= 1 +	a	+	a²	+ ... +	a^j	+ ....
1 – a. 1 – ax. 1 – ax²....		1 – x		1 – x. 1 – x²		1 – x. 1 – x².... 1 – x^j

The coefficient of a^jxⁿ in the expansion of

1

1 – a. 1 – ax. 1 – ax². ... 1 – axⁱ

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

Σ	1 – x^j+1. 1 – x^j+2. ... 1 – x^j+i	a^j.
	1 – x. 1 – x². ... 1 – xⁱ

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

1 – x^j+1. 1 – x^j+2. ... 1 – x^j+i	,
1 – x. 1 – x². ... 1 – xⁱ

which, observe, is unaltered by interchange of i and j.

Franklin has also similarly established the identity of Euler

	_{j = − ∞}
(1 – x)(1 – x²)(1 – x³) ... ad inf.	= Σ (−) jx^1/2(3j²+j),
	^{j = + ∞}

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 1/2(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 1/2(n – θ²) into θ or few parts, i.e. it is the coefficient of x^{1/2(n−θ²)} in

1	,
1 – x. 1 – x².1 – x³.... 1 – x^θ.

or of xⁿ in

x^θ21 – x². 1 – x⁴. 1 – x⁶. ... 1 – x^2θ,

⁠

and the whole generating function is

1 + $\sum _{\theta \ =\ 1}^{\theta \ =\ \infty }$	x^θ2	.
	1 – x². 1 – x⁴. 1 – x⁶. ... 1 – x^2θ

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^θxⁿ in the product (1 + ax) (1 + ax³) (1 + ax⁵) ... (1 + ax^2s+1) ..., and thence the coefficient of a^θ in this product is x^θ² / (1 – x². 1 – x⁴. 1 – x⁶ ... 1 – x^2θ), and we have the expansion

(1 + ax) (1 + ax³) (1 + ax⁵) ... ad inf. = 1 +	x	a +	x⁴	a² +	x⁹	a³ + ...
	1 – x²		1 – x². 1 – x⁴		1 – x². 1 – x⁴. 1 – x⁶

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^θxⁿ in the product (1 + ax) (1 + ax³) (1 + ax⁵) ... (1 + ax²ⁱ⁻¹); moreover the same number enumerates the partition of 1/2(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^{1/2(n−θ²)} in the expansion of