Page:EB1911 - Volume 06.djvu/779

1 – xi−θ+1. 1 – xi−θ+2. 1 – xi−θ+3. ... 1 – xi	,
1 – x. 1 – x2. 1 – x3. ... 1 – xθ

or of xⁿ 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 dimensions, and we have then a theory of a special kind of partition of multipartite numbers. Of such kind is theExtension to three dimensions. partition

 /(a₁a₂a₃...,  /(b₁b₂b₃...,  /(c₁c₂c₃..., ,  /...)

of the multipartite number

 /(a₁ + b₁ + c₁ + ..., a₂ + b₂ + c₂ + ..., a₃ + b₃ + c₃ + ..., ...)

if

a₁ ≥ a₂ ≥ a₃ ≥ ...; b₁ ≥ b₂ ≥ b₃ ≥ ..., ...
a₃ ≥ b₃ ≥ c₃ ≥ ...,

for then the graphs of the parts _{—————}
a₁a₂a₃..., _{—————}
b₁b₂b₃..., ... 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

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,

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

α₁ ≥ α₂ ≥ α₃ ≥ ... ... ≥ α_n

α₁ + α₂ + α₃ + ... + α_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 – x^s = (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

λ₁α₁ + λ₂α₂ + λ₃α₃ + ... ≥ 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 (p₁p₂p₃ ...) into parcels (m) is the coefficient of b^m(p₁p₂p₃ ...)xⁿ in the development of the Method of symmetric functions.fraction

1
	(1 − bαx. 1 − bβx. 1 − bγx ...	)
×	(1 − bα2x2. 1 − bαβx2. 1 − bβ2x2 ...	)
×	(1 − bα3x3. 1 − bα2βx3. 1 − bαβγx3 ...	)
......

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

1 + h_r1 bx^r + h_r2 b²x^2r + ... ,

we may write the development

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

and picking out the coefficient of b^m xⁿ we find

Σ h_τ1h_τ2h_τ3 ... ,

t₁ t₂ t₃ 

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 (p₁p₂p₃ ...) into exactly two parts. We find

h_2² = h₄ − h₃h₁ + h²2
h_3² = h₆ − h₅h₁ + h₄h₂
h_4² = h₈ − h₇h₁ + h₆h₂ + h₅h₃ + h²4,

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

h₂x² + h₂h₁x³ + (h₄ + h²2)x⁴ + (h₄h₁ + h₃h₂)x⁵ + (h₆ + 2h₄h₂)x⁶ + (h₆h₁ + h₅h₂ + h₄h₃)x⁷ + (h₈ + 2h₆h₂ + h²4)x⁸ + ...

Taking

h₄ + h²2 = h₄ + {(2) + (1²)}² = 2(4) + 3(31) + 4(2²) + 5(21²) + 7(1⁴),

the term 5(21²) 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 h_r^s has been studied. (See MacMahon, Proc. Lond. Math. Soc. vol. xix.) Putting x equal to unity, the function may be written (h₂ + h₄ + h₆ + ...) (1 + h₁ + h₂ + h₃ + h₄ + ...), 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, so that when the operator is performed upon the function a number is reached which enumerates the solutions Method of differential operators. 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