1 – x^{i−.mw-parser-output .grc{font-family:SBL BibLit,SBL Greek,DejaVu Sans,DejaVu Serif,FreeSerif,FreeSans,Athena,Gentium Plus,Gentium,Palatino Linotype,Arial Unicode MS,Lucida Sans Unicode,Lucida Grande,Code2000,sans-serif}.mw-parser-output .polytonic{font-family:"SBL BibLit","SBL Greek",Athena,"Foulis Greek","Gentium Plus",Gentium,"Palatino Linotype","Arial Unicode MS","Lucida Sans Unicode","Lucida Grande",Code2000}θ+1}. 1 – x^{i−θ+2}. 1 – x^{i−θ+3}. ... 1 – x^{i} | , |
1 – x. 1 – x^{2}. 1 – x^{3}. ... 1 – x^{θ} |
or of x^{n} in
1 – x^{2i−2θ+2}. 1 – x^{2i−2θ+4}. ... 1 – x^{2i} | xθ^{2}; |
1 – x^{2}. 1 – x^{4}. 1 – x^{6}. ... 1 – x^{2θ} |
hence the expansion
(1 + ax) (1 + ax^{3}) (1 + ax^{5}) ... (1 + ax^{2i−1}) = 1 + Σθ=iθ=1 | 1 – x^{2i−2θ+2}. 1 – x^{2i−2θ+4}. ... 1 + x^{2i} | x^{θ2} a^{θ}. |
1 – x^{2}. 1 – x^{4}. 1 – x^{6}. ... 1 – x^{2θ} |
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
(a_{1}a_{2}a_{3}..., (b_{1}b_{2}b_{3}..., (c_{1}c_{2}c_{3}..., , ...)
of the multipartite number
(a_{1} + b_{1} + c_{1} + ..., a_{2} + b_{2} + c_{2} + ..., a_{3} + b_{3} + c_{3} + ..., ...)
if
a_{1} ≥ a_{2} ≥ a_{3} ≥ ...; b_{1} ≥ b_{2} ≥ b_{3} ≥ ..., ...
a_{3} ≥ b_{3} ≥ c_{3} ≥ ...,
for then the graphs of the parts _{—————}
a_{1}a_{2}a_{3}..., _{—————}
b_{1}b_{2}b_{3}..., ... 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
α_{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 – 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
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_{1}p_{2}p_{3} ...) into parcels Method of symmetric functions. (m) is the coefficient of b^{m}(p_{1}p_{2}p_{3} ...)x^{n} 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
we may write the development
_{r = ∞} | |
Π | (1 + h_{r1} bx^{r} + h_{r2} b^{2}x^{2r} + ...), |
^{r = 1} |
and picking out the coefficient of b^{m} x^{n} we find
t_{1} t_{2} t_{3}
where
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_{1}p_{2}p_{3} ...) into exactly two parts. We find
h_{22} = h_{4} − h_{3}h_{1} + h^{2}2 |
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_{2}x^{2} + h_{2}h_{1}x^{3} + (h_{4} + h^{2}2)x^{4} + (h_{4}h_{1} + h_{3}h_{2})x^{5} + (h_{6} + 2h_{4}h_{2})x^{6} + (h_{6}h_{1} + h_{5}h_{2} + h_{4}h_{3})x^{7} + (h_{8} + 2h_{6}h_{2} + h^{2}4)x^{8} + ...
Taking
the term 5(21^{2}) 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_{2} + h_{4} + h_{6} + ...) (1 + h_{1} + h_{2} + h_{3} + h_{4} + ...), 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