Page:EB1911 - Volume 06.djvu/778

From Wikisource
Jump to navigation Jump to search
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νex)λ aλν eλx


is equal to the residue of

ΣΣΣ cλ, μ ,
(aμaνex)λ

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

ΣΣ cλ, μ ,
aλν (1 – ex)λ

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

ΣΣ cλ, μ ,
aλν

which proves the lemma.

Take F(x) = 1/xn (1 – xa) (1 – xb) ... (1 – xl) = ƒ(x)/xn, 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

Σ ρnenx ƒ(ρex) = Σ ρnenx .
(1 – ρaeax) (1 – ρbebx) ... (1 – ρlelx)

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

Σ ρnq enx ,
(1 – ρaq eax) (1 – ρbq ebx) ... (1 – ρlq elx)

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

Σ ρνq eνx ,
(ρ1/2aq e1/2axρ1/2aq e1/2ax) (ρ1/2bq e1/2bxρ1/2bq e1/2bx) ... (ρ1/2lq e1/2lxρ1/2lq e1/2lx)

and the calculation in simple cases is practicable.

Thus Sylvester finds for the coefficient of xn in

1
1 – x. 1 – x2. 1 – x3

the expression

ν2  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. (3213), 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 – ax2. 1 – ax3 ... ad inf. in ascending powers of a; for the coefficient of ajxn 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 xn in the ascending expansion of 1/(1 – x. 1 – x2 ... 1 – xj. Therefore

1 = 1 + a + a2 + ... + aj + ....
1 – a. 1 – ax. 1 – ax2.... 1 – x 1 – x. 1 – x2 1 – x. 1 – x2.... 1 – xj

The coefficient of ajxn in the expansion of

1
1 – a. 1 – ax. 1 – ax2. ... 1 – axi

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 – xj+1. 1 – xj+2. ... 1 – xj+i aj.
1 – x. 1 – x2. ... 1 – xi

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 – xj+1. 1 – xj+2. ... 1 – xj+i ,
1 – x. 1 – x2. ... 1 – xi

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

Franklin has also similarly established the identity of Euler

  j = − ∞
(1 – x)(1 – x2)(1 – x3) ... ad inf. = Σ (−) jx1/2(3j2+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(3j2 + 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 θ2 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 θ2 nodes is clearly equal to the number of partitions of 1/2(nθ2) into θ or few parts, i.e. it is the coefficient of x1/2(nθ2) in

1 ,
1 – x. 1 – x2.1 – x3.... 1 – xθ.
or of xn in
xθ2/1 – x2. 1 – x4. 1 – x6. ... 1 – x2θ,

and the whole generating function is

1 + xθ2 .
1 – x2. 1 – x4. 1 – x6. ... 1 – x2θ

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 θ2 nodes is the coefficient of aθxn in the product (1 + ax) (1 + ax3) (1 + ax5) ... (1 + ax2s+1) ..., and thence the coefficient of aθ in this product is xθ2 / (1 – x2. 1 – x4. 1 – x6 ... 1 – x2θ), and we have the expansion

(1 + ax) (1 + ax3) (1 + ax5) ... ad inf. = 1 + x a + x4 a2 + x9 a3 + ...
1 – x2 1 – x2. 1 – x4 1 – x2. 1 – x4. 1 – x6

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 θ2 nodes we have partitions enumerated by the coefficient of aθxn in the product (1 + ax) (1 + ax3) (1 + ax5) ... (1 + ax2i−1); moreover the same number enumerates the partition of 1/2(nθ2) into θ or fewer parts, of which the largest part is equal to or less than iθ, and is thus given by the coefficient of x1/2(nθ2) in the expansion of