COMBINATORIAL
ANALYSIS
157 conjugate is one into j parts, of which the largest is i, and The constant term is 22 , fj. we obtain the theorem:—“ The number of partitions of Let av be a value of x which makes the fraction infinite. The any number into . p^of fewer’ and haTin« tle residue of part . eclual t°j _ remains the same when the 222 +: equal or less than j, (a - avex)K a)/* numbers i and j are interchanged.” is equal to the residue of The study of this representation on a lattice (termed by C Sylvester the “ graph ”) yields many theorems similar to 222- A. x {a-ave Y that just given, and, moreover, throws considerable light and when v = the residue vanishes so that we have to consider upon the expansion of algebraic series. The theorem of reciprocity just established shows that the 22 number of partitions of n into j parts or fewer, is the same as the «A(i _ ex)k' number of ways of composing n with the integers 1, 2, 3, ...j. and the residue of this is, by the first lemma, Hence we can expand 1 — a. 1 — ax. 1— ax2. 1 — ax?... ad inf. C ascending powers of a ; for the coefficient of aJ'xn in the expansion - 22'- A, fj. 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 expanwhich proves the lemma. sion of l-x. 1— 1 -cc2. ...1r -xP'Therefore Take Fa:= since tIie 801,8111 number is its constant term. 1 — a.l-acc.l — ax2. -=1 + : ■X ^ 1i -23. 1T - + ... Let p be a root of unity which makes fx infinite when substicd2 tuted for x. The function of which we have to take the residue is 1 23 . 1 23 1 - 2>’ n nx x Xp- e f(pe~ ) The coefficient of a3xn in the expansion of _2 P Kg™* , 1 (1 — pae~ax)(l — pbe~bx)... (1 -ple~lx)' l-a.l-a2:.l - ax2.... 1 - ax’ We may divide the calculation up into sections by considering denotes the number of ways of composing n withy or fewer parts, separately that portion of the summation which involves the none of which are greater than i. The expansion is known to be primitive gth roots of unity, q being a divisor of one of the ^1 -a^*-1. l-xt*2. ...1 -2^+i , numbers a, l, ...l. Thus the gth wave is 1 -23. 1 -2i2. ...1 -23* - - 11-71X It has been established by the constructive method by F. Franklin {Amcr. Jour, of Math. vol. v. p. 254), and shows that the generat(1 -pV6*) ... (l-plqe-1*) ing function for the partitions in question is 1 — 2^+1. 1 —23-?+2. ...1 -2^+i which, putting — for pq and v = n + [a + 'b +... +1), may be written Pi 1 -23 . 1 -232 . ...1 — 23* ’ pvevX which, observe, is unaltered by interchange of i and j. Franklin has also similarly established the identity of Euler— ~ - p-&e-iax^pibeibx _ p-$be-lbx^ ___ - p-¥ e-^ J = - 00 and the calculation in simple cases is practicable. (l-23)(l-2;2)(l- 233) ad inf. = 2( n Thus Sylvester finds for the coefficient of x in j=+ CO 1 2 known as the “pentagonal number theorem,” which on interpretation shows that the number of ways of partitioning n into an 1-x. l-x .l -x3 even number of unrepeated parts is equal to that into an uneven v2 7 1 1 number, except when n has the pentagonal form {3j2+j), j posithe expression 12 “ 72 " 8 ^ ^ + 9 + p3" 0 tive or negative, when the difference between the numbers of the where v=n + 3. partitions is ( - /. To illustrate an important dissection of the graph we will conSylvester, Franklin, Durfee, Ely, and others, have sider those graphs which read the same by columns as by lines ; evolved a Constructive Theory of Partitions, the object of these are called self-conjugate. Such a graph may be obviously which is the contemplation of the partitions dissected into a square, containing Sylvester’s themselves, and the evolution of their properties say d2 nodes, and into two graphs, one lateral and one subjacent, the ^Method*11 fr°m a sf^dy of their inherent characters. It latter being the conjugate of the is concerned for the most part with the parti- former. The former graph is limited tion of a number into parts drawn from the natural to contain not more than 6 parts, series of numbers 1, 2, 3 Any partition, say (521) but is subject to no other condition. Hence the number of self-conjugate of the number 8, is represented by nodes placed in order partitions of n which are associated at the points of a rectangular lattice, with a square of 02 nodes, is clearly equal to the number of partitions2 of {n d2) into 6 or few parts. i.e., it is the coefficient of x¥a-Q ) in
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 of conjugacy was first pointed out by Ferrers. If the original partition is one of a number n in i parts, of which the largest is j, the
1 — 23 . 1 - 232 . 1 - 233 1 - 230 .’ 2302 or of 23n in 2 4 1 - 23 . 1 — 23 .1 - 236 1 — X26 ’ and the whole generating function is 9= co 2302 1+2 2 4 6 = 1 1— 23 . 1 — 23 . 1- 236 ....1 — 232 Now the graph is also composed of 0 angles of nodes, each angle containing an uneven number of nodes ; hence the partition is transformable into one containing 0 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 02 nodes is the coefficient
