Open main menu
This page has been proofread, but needs to be validated.
757
COMBINATORIAL ANALYSIS
1 – xiθ+1. 1 – xiθ+2. 1 – xiθ+3. ... 1 – xi ,
1 – x. 1 – x2. 1 – x3. ... 1 – xθ

or of xn in

1 – x2i−2θ+2. 1 – x2i−2θ+4. ... 1 – x2i xθ2;
1 – x2. 1 – x4. 1 – x6. ... 1 – x2θ

hence the expansion

(1 + ax) (1 + ax3) (1 + ax5) ... (1 + ax2i−1) = 1 + Σθ=iθ=1 1 – x2i−2θ+2. 1 – x2i−2θ+4. ... 1 + x2i xθ2 aθ.
1 – x2. 1 – x4. 1 – x6. ... 1 – x2θ

There is no difficulty in extending the graphical method to three Extension to three dimensions. dimensions, and we have then a theory of a special kind of partition of multipartite numbers. Of such kind is the partition

 /(a1a2a3...,  /(b1b2b3...,  /(c1c2c3..., ,  /...)

of the multipartite number

 /(a1 + b1 + c1 + ..., a2 + b2 + c2 + ..., a3 + b3 + c3 + ..., ...)

if

a1a2a3 ≥ ...; b1b2b3 ≥ ..., ...
a3b3c3 ≥ ...,

for then the graphs of the parts —————
a1a2a3...,
—————
b1b2b3...,
... are superposable, and we have what we may term a regular graph in three dimensions. Thus the partition (643, 632, 411) of the multipartite (16, 8, 6) leads to the graph


EB1911 Combinatorial Analysis, partition graph.jpg

and every such graph is readable in six ways, the axis of z being perpendicular to the plane of the paper.

Ex. Gr.

Plane parallel to xy, direction Ox reads (643, 632, 411)
 ”   ” xy,   ” Oy  ” (333211, 332111, 311100)
 ”   ” yz,   ” Oy  ” (333, 331, 321, 211, 110, 110)
 ”   ” yz,   ” Oz  ” (333, 322, 321, 310, 200, 200)
 ”   ” zx,   ” Oz  ” (333322, 322100, 321000)
 ”   ” zx,   ” Ox  ” (664, 431, 321)

the partitions having reference to the multipartite numbers 16, 8, 6, 976422, 13, 11, 6, which are brought into relation through the medium of the graph. The graph in question is more conveniently represented by a numbered diagram, viz.—

3 3 3 3 2 2
3 2 2 1    
3 2 1      

and then we may evidently regard it as a unipartite partition on the points of a lattice,

EB1911 Combinatorial Analysis, lattice.jpg

the descending order of magnitude of part being maintained along every line of route which proceeds from the origin in the positive directions of the axes.

This brings in view the modern notion of a partition, which has enormously enlarged the scope of the theory. We consider any number of points in plano or in solido connected (or not) by lines in pairs in any desired manner and fix upon any condition, such as is implied by the symbols ≥, >, =, <, ≤, ≷, as affecting any pair of points so connected. Thus in ordinary unipartite partition we have to solve in integers such a system as

α1α2α3 ≥ ... ... ≥ αn

α1 + α2 + α3 + ... + αn = n,

the points being in a straight line. In the simplest example of the three-dimensional graph we have to solve the system

α1α2  
≚ ≙ α1 + α2 + α3 + α4 = n,  
α3α4  

and a system for the general lattice constructed upon the same principle. The system has been discussed by MacMahon, Phil. Trans. vol. clxxxvii. A, 1896, pp. 619-673, with the conclusion that if the numbers of nodes along the axes of x, y, z be limited not to exceed the numbers m, n, l respectively, then writing for brevity 1 – xs = (s), the generating function is given by the product of the factors

        x
 (l + 1) . (l + 2) .... (l + m)
(1) (2) (m)
(l + 2) . (l + 3) .... (l + m + 1)
(2) (3) (m + 1)
.   . .... .
.   . .... .
.   . .... .
(l + n) . (l + n + 1) .... (l + m + n – 1)
(n) (n + 1) (m + n – 1)
y        

one factor appearing at each point of the lattice.

In general, partition problems present themselves which depend upon the solution of a number of simultaneous relations in integers of the form

λ1α1 + λ2α2 + λ3α3 + ... ≥ 0,

the coefficients λ being given positive or negative integers, and in some cases the generating function has been determined in a form which exhibits the fundamental solutions of the problems from which all other solutions are derivable by addition. (See MacMahon, Phil. Trans. vol. cxcii. (1899), pp. 351-401; and Trans. Camb. Phil. Soc. vol. xviii. (1899), pp. 12-34.)

The number of distributions of n objects (p1p2p3 ...) into parcels Method of symmetric functions. (m) is the coefficient of bm(p1p2p3 ...)xn in the development of the fraction

1
  (1 − bαx. 1 − bβx. 1 − bγx ... )
× (1 − bα²x². 1 − bαβx². 1 − bβ²x² ... )
× (1 − bα³x³. 1 − bα²βx³. 1 − bαβγx³ ... )
......

and if we write the expansion of that portion which involves products of the letters α, β, γ, ... of degree r in the form

1 + hr1 bxr + hr2 b2x2r + ... ,

we may write the development

r = ∞
Π (1 + hr1 bxr + hr2 b2x2r + ...),
r = 1

and picking out the coefficient of bm xn we find

Σ hτ1hτ2hτ3 ... ,

t1t2t3

where

Σ τ = m, Σ rt = n.

The quantities h are symmetric functions of the quantities α, β, γ, ... which in simple cases can be calculated without difficulty, and then the distribution function can be formed.

Ex. Gr.—Required the enumeration of the partitions of all multipartite numbers (p1p2p3 ...) into exactly two parts. We find

h22 = h4h3h1 + h22
h32 = h6h5h1 + h4h2
h = h8h7h1 + h6h2 + h5h3 + h24,

and paying attention to the fact that in the expression of hr2 the term h2
r
is absent when r is uneven, the law is clear. The generating function is

h2x2 + h2h1x3 + (h4 + h22)x4 + (h4h1 + h3h2)x5 + (h6 + 2h4h2)x6 + (h6h1 + h5h2 + h4h3)x7 + (h8 + 2h6h2 + h24)x8 + ...

Taking

h4 + h22 = h4 + {(2) + (12)}2 = 2(4) + 3(31) + 4(22) + 5(212) + 7(14),

the term 5(212) indicates that objects such as a, a, b, c can be partitioned in five ways into two parts. These are a | a, b, c; b | a; a, c; c | a, a, b; a, a | b, c; a, b | a, c. The function hrs has been studied. (See MacMahon, Proc. Lond. Math. Soc. vol. xix.) Putting x equal to unity, the function may be written (h2 + h4 + h6 + ...) (1 + h1 + h2 + h3 + h4 + ...), a convenient formula.

The method of differential operators, of wide application to problems of combinatorial analysis, has for its leading idea the designing of a function and of a differential operator, Method of differential operators. so that when the operator is performed upon the function a number is reached which enumerates the solutions of the given problem. Generally speaking, the problems considered are such as are connected with lattices, or as it is possible to connect with lattices.

To take the simplest possible example, consider the problem of finding the number of permutations of n different letters. The