Page images
PDF
EPUB

Let (T1 T2 T3

m!

...

...

m!

TT1, T2, T3

ay an

[ocr errors]

1

, T2T3

) be a partition of m

when tı, t2, &c., are put equal to unity, is equal to the coefficient Case II. (2772723...) a partition of n.

of the same term in the product of the whole number of distributions of the n objects, there

1 (2a, +az+...+a)'(2a;+2a2+ ... +a.).... (2a,+2a2+ ... +2a,). will be a certain number such that 11 parcels each contain Pi

This result gives a direct connexion between the number of objects, and in general Ts parcels each contain pg objects where compositions and the permutations of the letters in the product s=1, 2, 3, .... Consider the product h"1","3 which can be aplan... asSelecting any permutation, suppose that the letter ar

P1 P2 P3 perinuted in

For each of these ways

occurs q, times in the last pr+Pr+1+ +Ps places of the permuways. TT1! Try!TI3!...

tation ; the coellicient in question may be represented by will be a distribution function for distributions of 1229+42+...+9s, the summation being for every permutation, P1 P2 P3 the specified type. Hence, regarding all the permutations, the

and since qı=P, this may be written distribution function is

2P1 - 18242+13+...+98.

Ex. Gr.–For the bipartite 22, P2=P2=2, and we have the followTT! Try!Try!... "p1"p2"p3

ing scheme :and regarding, as well, all the partitions of n into exactly m parts,

ai ai

A.2 A2 92=2 the desired distribution function is

di a2

ai (2 m!

a. ai [ET=m, Etp=n],

aga,

a a =1 T !12! T3!... "P1 P2 P3

A2 a 0.2 ai that is, it is the coefficient of an in (h120 + h.222 +1323 + ...)m. The

d2 da ai ai

=0 value of A 1 2 2.3...), (1") is the coefficient of (72722222... )2" Hence F (22)=2 (22+2+2+2+2+2°)= 26.

We may regard the fraction in the development of the above expression, and is easily shown to have the value

1. {1 - tı(201+as+...+as)} {1 – tz(201+2a2+... tas)}... {1 - tg(2a1 +222 +...+2a,)}

as a redundant generating function, the enumeration of the
P1
1+m-1 P2+ m - 1

compositions being given by the coefficient of
P1
12
P3

(t, a,}{{ga,... (1,2,)
P2+M -
P3 + m - 2

The transformation of the pure generating function into a factor-
P1
P2
1'3

ized redundant form supplies the key to the solution of a large
Pi+m - 3
P2+ m - 3
P3+m-3)

number of questions in the theory of ordinary permutations, as
P1
P2
P3

will be seen later.
to m terms.

[The transformation of the last section involves

The Theory Observe that when P1=P2=Pg=...=T1=T,==... =1 this ex a comprehensive theory of Permutations, which of Permupression reduces to themth divided difference of oř. The expression it is convenient to discuss shortly here.

tations. gives the compositions of the multipartite number 212

If X1, X2, X3, X, be linear functions given by the matricular

relation
into m parts. Summing the distribution function from m=1 to
m="o and putting x=1, as we may without detriment, we find

(Xį, X2,
Xn)= (0,11 012

din) (x1, x2,

021 (122 that the totality of the compositions is given by

hi+ha+h3+...

1-11 12 13 which may be given the form

01-02 + Az - .
1-2(az - Az+az - ...)

Adding } we

that portion of the algebraic fraction, bring this to the still more convenient form

1
1
11 – 2(07–49+03 - ...)

(1 - 87 X1) 1 - sz.X2) ... (1 – 5, \n)'

which is a function of the products sz, s.979, 83X3 ... Snan only is Let F(php?.?...) denote the total number of compositions of

1 1 the multipartite Pa P3-P3

= 1 + 1 (p)a", and |(1 - 11800) (1 - (223,22)(1 - 2335;&g) ... (1 - Annnn) |

where the denominator is in a symbolic form and denotes on 1 2P-1-1 aß

} + EFa

1- |21|821+]211222 | S19971.29 - ...+(-)"\0110m2(133...Ann ($189...S91182...In, and expanding the left-hand side we easily find

where laul, la 0221, ... |( 11022 ... Annl denote the several co-axial

(Pi+P2-1)! F(P122) =2P1+P2–1 (P1+P2)! – 2P1+P2 - 2,

minors of the determinant
0! P!PA!
1 !(P1 - 1)!(P2 - 1)!

lang...ann!
(P.+P2-2)!
2 !(P1 - 2)! (22 - 2)!

of the matrix. (For the proof of this theorem see MacMahon,

“A certain Class of Generating Functions in the Theory of We have found that the number of compositions of the multi- Numbers,” Phil. Trans. R. S. vol. clxxxv. A, 1891). It follows partite P.P2P3... p, is equal to the coefficient of symmetric function that the coefficient of (P1P2P3... Ps) or of the single term amamma

als in the development

in the product according to ascending powers of the algebraic fraction

(211-22+1979+..+ainan)$1(02171+Conte+..+aznen)€9..(ani”ı+Ameta +..+annan)$" 1 1. 1-2(Zan - Layan + Ea,2,A3 - ...+( - )s+lajaga, ... asi

is equal to the coefficient of the same tern in the expansion This result can be thrown into another suggestive form, for it

ascending-wise of the fruction

1 can be proved that that portion of the expanded fraction

1- Elaulci+21010921 21:29 ... +(-,"1414.02...(InnXyXg...Xn }-{1–1(2aytaxt...+a,)} {1–t3(2a7+2a3...+a;) ... {1 – 6,(2aj+%azt...+2a;}' If the elements of the determinant be all of them equal to unity,

we obtain the functions which enumerate the unrestricted permuwhich is composed entirely of

tations of the letters in tai, tzan, tgaz, ... tgas has the expression 1.

viz.,

(x1+x2+

„€ 1-2(tja1 - Stītuajas+stītetzayana3-...+(-)s+ltīt2...tsajaa ... as)' and therefore the coefficient of a

al's in the latter fraction,

and

1-(x1+x+

+xn)

[ocr errors]

anl (172

[ocr errors]

Tl T2 T3

Then 11-20

+2P1+P2-3

[ocr errors]

n

...a

[ocr errors]
[ocr errors][merged small][merged small][merged small][merged small][merged small]

1

1

0
1

1 1

[ocr errors]

-1

1

n-2

...=n.

Suppose that we wish to find the generating function for the the collection, termed the parts of the partition, in descending enumeration of those permutations of the letters in 2012...e in order of magnitude, and to indicate repetitions of the same part which are such that no letter x, is in a position originally occupied (3213). Euler's pioneering work in the subject rests on the observaby an xg for all values of s. This is a generalization of the “Problème des rencontres” or of

tion that the algebraic multiplication

derangements.” We have merely to put

24 x cò x 29 x ...=ca+b+c+...
du=222=233= .
=ann = 0

is equivalent to the arithmetical addition of the exponents and the remaining elements equal to unity.

a, b, c, He showed that the number of ways of composing n

The generating with ý integers drawn from the series a, b, c, ...? product is

repeated or

not, is equal to the coefficient of spain in the ascending expansion (22+2+...+)$(+2y + ... + 2n)$2...(22+2 + ... + 2n-1)$", of the fraction and to obtain the condensed form we have to evaluate the co-axial minors of the invertebrate determinant

1- šva. 1 - Šab.1 - Sacc...,'

. 1 10 1

which he termed the generating function of the partitions in 1 1

question. 1

If the partitions are to be composed of p, or fewer parts, it is 1 1 1 Ő

merely necessary to multiply this fraction by Similarly, if The minors of the 1st, 2nd, 3rd ... nth orders have respectively the

the parts are to be unrepeated, the generating function is the values

algebraic product

(1+522)(1+ 3x) (1 + 50cc) ...,

if each part may occur at most twice, +2

(1+Bora + 3222a)(1+ Sub + 522,20)(1+30° +522:20) ... (-)-(n-1),

and generally if each part may occur at most 1:-1 times it is therefore the generating function is

1-3kka 1-5km kb 1 - 52.ke
1-sinu
1 -

1- Soco 1 - Ex X2 – 24x Calz – - sEx122... Xs1 - -(n-1). K2...xn

It is thus easy to form generating functions for the partitions of

numbers into parts subject to various restrictions. If there be no or writing

restriction in regard to the numbers of the parts, the generating (2 – x1)(x – X,)... (x – Xn)=wn – Q72n–1+m

function is this is

1 1

1-29. 1 - 25.1 - 200. ... 1-02-203 – 384 - (1 - 1)an

and the problems of finding the partitions of a number n, and of Again, consider the general problem of “ derangements." We

determining their number, are the same as those of solving and have to find the number of permutations such that exactly m of cnumerating the solutions of the indeterminate equation in the letters are in places they originally occupied. We have the positive integers particular redundant product

ax+by+cm+

Euler considered also the question of enumerating the solutions (ax,+x2 + ... +29)$1(x2 + axz+ +2,582...(xz+i@g+ ... + axn)$N, of the indeterminate simultaneous equation in positive integers in which the sought number is the coefficient of a" w 12.5

ax +by+c= +...=n The true generating function is derived from the determinant

a'x +b'y+c': +...=n'

a'x+"y+cz +...
a 1 1
1

which was called by him and those of his time the “Problem of 1

the Virgins.” The enumeration is given by the coefficient of xryn'"... in the expansion of the fraction

1 and has the form

(1 – zaryb.zc...)(1 – ura'yo.zc...)(1 – zva”yoze"...)...

which enumerates the partitions of the multipartite number l-a£rı+(a – 1)(a+1)x119 -.. +(-)"(a – 1)n-/(a+n – 1)r189...In.

un'n"... into the parts It is clear that a large class of problems in permutations

abc ... , u'l'c'..., al'c ......... can be solved in a similar manner, viz., by giving special Sylvester has determined an analytical expression for the covalues to the elements of the determinant of the matrix.

efficient of an in the expansion of The redundant product leads uniquely to the real generat

1 ing function, but the latter has generally more than one

(1 - 4")(1-2)... (1-2) representation as a redundant product, in the cases in

To explain this we have two lemmas :which it is representable at all. For the existence of a redundant form, the coefficients of 21, 22, ... X7°29

in Lomma 1.—The coefficient of

a

i.e., after Cauchy, the residue the denominator of the real generating function must satisfy in the ascending expansion of (1 – (*)-* is -1. For when i is unity, 2n – no +n - 2 conditions, and assuming this to be the it is obviously the case, and case, a redundant form can be constructed which involves

(1 – 67)-i-1=(1 – 62)-1 +ex(1 – 6X)-i-1 n- 1 undetermined quantities. We are thus able to pass

d from any particular redundant generating function to

=(1 – 6)=i+ diz one equivalent to it, but involving n-1 undetermined Here the residue of

d

1 quantities. Assuming these quantities at pleasure we

da obtain a number of different algebraic products, each of of (1 – 67)-, is unchanged when i is increased by unity, and is, which may have its own meaning in arithmetic, and thus therefore, always – 1 for all values of i.

Le'mma 2.—The constant term in any proper algebraical fraction the number of arithmetical correspondences obtainable is developed in ascending powers of its variable is the same as the subject to no finite limit (cf. MacMahon, loc. cit., pp. 125 residuo with changed sign, of the sum of the fractions obtained et seq.)]

by substituting in the given fraction, in lieu of the variable, its

exponential multiplied in succession by each of its values (zero 3. The Theory of Partitions. Parcels defined by (m). — When an excepted, if there be such), which makes the given fraction infinite. Case III.

ordinary unipartito number n is broken up into other For write the proper algebraical fraction

numbers, and the order of occurrence of the numbers is immaterial, the collection of numbers is termed a partition of

Fæ=es

YX the number n. It is usual to arrange the numbers comprised in

(am - 2)

...=n"

1

.

1

1
1
1

a
1
1

[ocr errors]

1

a

[ocr errors]

1

[ocr errors][merged small][merged small]

ΣΣ ,μ

[ocr errors]
[ocr errors]
[ocr errors]

р M

[ocr errors]
[ocr errors]
[ocr errors]

1-X.

1

[ocr errors]
[ocr errors]

-X.

1

conjugate is one into j parts, of which the largest is i, and The constant term is al

we obtain the theorem : “ The number of partitions of Let a, be a value of a which makes the fraction infinite. The

i parts

any number into residue of

i parts or fewer, and having the largest Ca, M

equal to j ΣΣΣ

part

remains the same when the amena

equal or less than j,

numbers i and j are interchanged.” is equal to the residue of

The study of this representation on a lattice (termed by

Sylvester the “graph”) yields many theorems similar to ΣΣΣ. (aju – a,etja?

that just given, and, moreover, throws considerable light and when v=u, the residue vanishes so that we have to consider upon the expansion of algebraic series.

The theorem of reciprocity just established shows that the ΣΣ. a (1-ety?

number of partitions of n into j parts or fewer, is the same as the number of ways of composing n with the integers 1, 2, 3, ...j.

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

Hence we can expand

in 1 .- a.l-ax. 1-ar-.1-axö... ad inf. ascending powers of a ; for the coefficient of aircn 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 an in the ascending expanwhich proves the lemma.

1 sion of

Therefore 1

foc Take Fx=

since the sought

22....1-W* 20"(1 - 204)(1-2) (1 – 20)

1

ri2

-=1+ number is its constant term.

1-a.1-ax. 1 - ax....

1-2

1-X Let p be a root of unity which makes fæc infinite when substi

ai tuted for a. The function of which we have to take the residue is

+
1
2.

+ ..., Ep-nentf(pe-)

The coefficient of afwn in the expansion of

1

p-nenz
(1 - pae-us)(1 - pe-60) ... (1 - ple-1x)"

1-a.l-ax. 1 - axa.... 1- axé We may divide the calculation up into sections by considering denotes the number of ways of composing n with j 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 qth roots of unity, a being a divisor of one of the numbers a, b, ...l. Thus the qth wave is

1 - +1.1 – 20+2. ...1 - vw+i
2

-ậ,
1 -2.1-2.... 1-ci

It has been established by the constructive method by F. Franklin Σ (1 - pohle - Ax) (1 – pie- bz)... (1-pie-hoy

(Amer. Jour. of Math. vol. v. P. 254), and shows that the generat

ing function for the partitions in question is
1
which, putting and v=n+f(a+b+...+1), may be written

1-23+1.1 -- ni+2.... 1 - aci+i
Pa
P1

1-X.1-x.... 1- qui

which, observe, is unaltered by interchange of i and j.
- 10e - fax (05be3b.c

By con
Pa

Franklin has also similarly established the identity of Eulerfbe- 368) ... (petable - p7226-328)

j= - 00 and the calculation in simple cases is practicable.

(1 – x)(1 – 22)(1 – 29)... ad inf. =E( – Yz?(32+), Thus Sylvester finds for the coeflicient of an in

j=+ 1

known as the “pentagonal number theorem,” which on interpre1-2.1-2.1-23

tation shows that the number of ways of partitioning n into an 7

even number of unrepeated parts is equal to that into an uneven 1 the expression (-)r + (8 +P5")

number, except when n has the pentagonal form }(3j2 +j), į posi12 72 8

tive or negative, when the difference between the numbers of the where y=n+3.

partitions is (- P. Sylvester, Franklin, Durfee, Ely, and others, have

To illustrate an important dissection of the graph we will con

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 02 nodes, and into two graphs, Saphical from a study of their inherent characters. It

one lateral and one subjacent, the Method

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 0 parts, series of numbers 1, 2, 3 .... Any partition, say (521) but is subject to no other condition. of the number 8, is represented by nodes placed in order Hence the number of self-conjugate at the points of a rectangular lattice,

partitions of n which are associated
with a square of 02 nodes, is clearly
equal to the number of partitions of }(n - 02) into 0 or few parts,
i.e., it is the coefficient of x(n – 02) in

1
1-2.1-2.1- 203 ....1 - 20

P, "еп

for

[ocr errors]

pert

[ocr errors]
[ocr errors][ocr errors]

202

202

or of an in

1-2.1-304.1-26....1-2:20 » and the whole generating function is

A= when the partition is given by the enumeration of the

1+ nodes by lines. If we enumerate by columns we obtain

0=1 1 - ca. 1-2t. 1 - 26 ....1 - 220* another partition of 8, viz., (3213), which is termed the Now the graph is also composed of O angles of nodes, each angle conjugate of the former. The fact of conjugacy was first containing an uneven number of nodes; hence the partition is pointed out by Ferrers. If the original partition is one

transformable into one containing o unequal uneven numbers. In

the case depicted this partition is (17 5, 1). Hence the number of a number n in i parts, of which the largest is j, the of the partitions based upon a square of 62 nodes is the coefficient

[ocr errors]

ad inf.

[ocr errors]

a +

1

1 - .

a

[ocr errors]

in

202

[ocr errors]
[ocr errors]
[ocr errors]

202

[ocr errors]

(2)

...)

1-x2.1-x+.1-2.0+

ti ta- tio

of aoxn in the product (1+ax)(1+ax3)(1+ax") (1+ax2s+1)..., every line of route which proceeds from the origin in the positive and thence the coefficient of an in this product is

directions of the axes.

This brings in view the modern notion of a partition, which has and we have the expansion

enormously enlarged the scope of the theory. We consider any 1-22.1-24.1 – 26. ...1 – 2020'

number of points in plano or in solido connected (or not) by lines (1+ax)(1+ax)(1+ axb)

in pairs in any desired manner and fix upon any condition, such

as is implied by the symbols, ~, >,='<,, , as affecting 24

29 =1+

any pair of points so connected. Thus in ordinary unipartite 1-act

partition we have to solve in integers such a system as Again, if we restrict the part magnitude to i, the largest angle of

a = a, az

> an nodes contains at most 2i – 1 nodes, and based upon a square of

ai + a2 + az + +an=, 02 nodes we have partitions enumerated by the coefficient of

the points being in a straight line. In the simplest example of in the product (1+ax)(1+axo)(1+ax) ... (1+axei – 1); moreover the three-dimensional graph we have to solve the system the same number enumerates the partition of 3(n- 02) into 0 or fewer parts, of which the largest part is equal to or less than i 0,

di = 42
as a

lv and is thus given by the coefficient of ał(n –02) in the expansion of

a + a2 + az +24=n,

Az = 24 1 - ri – 0+1.1 - æi – 0+2.1 - ci – 0+3.... 1- aci

and a system for the general lattice constructed upon the same 1-X.1-2.1-23. 1-20

principle. The system has been discussed by MacMahon, Phil. 1-221 – 20+2.1 – 221 – 20+4 ....1 - 221

Trans. R. S. vol. clxxxvii. A, 1896, pp. 619-673, with the or of an in

conclusion that if the numbers of nodes along the axes of x, y, 1 - x2.1 - v1.1-26 ... 1 - 220

be limited not to exceed the numbers m, n, 2 respectively, then hence the expansion

writing for brevity 1 – xo=(s), the generating function is given by the

product of the factors (1+ax)(1+ax3)(1 + a2") ... (1+ax2i – 1)

1 - 221 – 20+2.1- 2i – 20+4 =1+ E

(2+1) (1+2)

(1+ m) 1-2.1-.1 – 26. ...1 - 220

(1)

(m) There is no difficulty in extending the graphical method to

(2+2). (1+3)

(2+ m +1) Extension three dimensions, and we have then a theory of a

(2) (3)

(m+1) to three

special kind of partition of multipartite numbers. Of

such kind is the partition Dimensions. (aya.az 64b2b3 ... , 4C2C3 ... , ...)

(1+n) (1+1+1) (1+m+n - 1) of the multipartite number

(n) (n+1)

(11 +1 -1) (a +61+ci+ A2+bx+c2+ Ag+ + c3 +

y if dj + d2 = Az = ...; b. = b = b;=

one factor appearing at each point of the lattice. As-bscs...,

In general, partition problems present themselves which depend

upon the solution of a number of simultaneous relations in integers for then the graphs of the parts a7d9kz byb,63

are super

of the form posable, and we have what we may term a regular graph in three

Nyai +1242 +1323 +...0, dimensions. Thus the partition (643, 632, 411) of the multi

the coefficients 1 being given positive or negative integers, and in partite (16,8,6) leads to the graph

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. R. S. 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 (m) is the coefficient of lm (??1P21'3 ... Jac" in the development of the fraction.

Method of 1

Symmetric Y

Functions.

(1 – bax. 1 - bßx. 1-byit... and every such graph is readable in six ways, the axis of being

x (1 baʼvo. 1 - babxa. 1–18v2 ... perpendicular to the plane of the paper.

x (1 baox3.1 baB03.1- babyx3...) Ex, Gr. Plane parallel to xy, direction Ox reads (613,632,411)

and if we write the expansion of that portion which involves pro

ducts of the letters a, B, 7,
XY,
Oy (333211,332111,311100)

of degree r in the form
Y%,

Оy
(333,331,321,211,110,110)

1+,,bx" + h_222r + ...,
Y,

O: (333,322,321,310, 200, 200) we may write the development
,

Oz (333322,322100,321000)
X,
0.C (664,431,321)

II (1+), 62" + h__1222* +...),
the partitions having reference to the multipartite numbers 16, 8, 6,
976422, 13, 11, 6, which are brought into relation through the

and picking out the coefficient of bm " we find medium of the graph. The graph in question is more conveniently

sh, h_h represented by a numbered diagram, viz.3 2 2

where

Et=m, Ett=n.
1
1

The quantities h are symmetric functions of the quantities a, b, y,...

which in simple cases can be calculated without dilliculty, and and then we may evidently regard it as a unipartite partition on then the distribution function can be formed. the points of a lattice,

Ex. gr.—Required the enumeration of the partitions of all 0

multipartite numbers (P2P2P3 ...) into exactly two parts. We find

1,2=ht- h3h +
hig2=ho hihi+hisha

1,2=hy - Nya+hehe - hzhg+ha,

and paying attention to the fact that in the expression of h2, the y

term h, is absent when r is uneven, the law is clear. The the descending order of magnitude of part being maintained along generating function is

[ocr errors]

O

O

[merged small][ocr errors][merged small][merged small][merged small][merged small][merged small][merged small][ocr errors]

2

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

1

now

hyu2 +hqh12c3+(h4+13)2+ +(1.484+Nz12)200 + (H6+2hqh2) 26 ) and the law by which the operation is performed upon the pro

duct shows that the solutions of the given problem are enumer+(hghty+hpha + highs).7+(18+ 2hcha +11)x8 +

ated by the number A, and that the process of operation actually Taking ha+ha=24+ {(2)+(12)}?

represents each solution. =2(4)+3(31)+4(22) + 5(212)+7(14),

Ex. Gr. Take 1 =3, A2=2, 1=1,

PI=2, 22=2, P=1, 14=1, the term 5(212) indicates that objects such as a, a, b, c can be partitioned in five ways into two parts. These are ala, b, c;

D D azaz = 8, bla, a, c; ca, a, b; à, alb, c; a, bla, c. The function hys has and the process yields the eight diagrams : been studied. (See MacMahon, Proc. Lond. Math. Soc. vol. xix.) Putting ac equal to unity, the function may be written 1 1

11 (ha+ha+he+ ...)(1+hy+hy+h; +he+ ...), a convenient formula.

1 1

1
1

1 1 The method of Differential Operators, of wide applica

1 tion to problems of combinatorial analysis, has for its

leading idea the designing of a function and of Method of

a differential operator, so that when the operaDifferential Operators. tor is performed upon the function a number

1 1 is reached which enumerates the solutions of the given problem. Generally speaking, the problems 1 1

1 1 considered are such as are connected with lattices, or that

1

1 it is possible to connect with lattices.

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

d

, of the problem dx

symmetry in the theory of Symmetric Functions. on=n! the number which enumerates the permutations. In For the next example we have a similar problem, but no fact

restriction is placed upon the magnitude of the numbers which Ozn = Ox.2.2.3.4.2....,

may appear in the compartments. The function is and differentiating we obtain a sum of n terms by striking out an

hay hd2 ... ham, ham being the homogeneous product sum of the e from the product in all possible ways. Fixing upon any one of quantities a, of order 1. The operator is as before these terms, say x.t.2.2...., we again operate withi or by striking

Dr, Dp, ... Dm out an x in all possible ways, and one of the terms so reached is 2.4.2.4.2..... .... Fixing upon this term, and again operating and

and the solutions are enumerated by continuing the process, we finally arrive at one solution of the

D, D,
PP2

D,

??,????, ... Hami problem, which taking say n=4) may be said to be in correspondence with the operator diagram

Putting as before 11=3, 12=2, 1;=1, P1=2, P2=2, P3=1, P4=1,

the reader will have no difficulty in constructing the diagrams ox

of the eighteen solutions.

The next and last example of a multitude that might be given Oze

1

shows the extraordinary power of the method by solving the

famous problem of the Latin Square,” which for hundreds of Oz

years had proved beyond the powers of mathematicians. The oz

problem consists in placing n letters a, b, c, ... n in the compartments of a square lattice of no compartments, no compartment

being empty, so that no letter occurs twice either in the same the number in each row of compartments denoting an operation row or in the same column. The function is here of or. Hence the permutation problem is equivalent to that of placing n units in the compartments of a square lattice of order

2n-1 2-2

a. n in such manner that each row and each column contains a single unit. Observe that the method not only enumerates, but

and the operator D’n the enumeration being given by also gives a process by which each solution is actually formed. The same problem is that of placing n Rooks upon a chess-board of 22 compartments, so that no Rook can be captured by any

Dn other Rook.

Regarding these elementary remarks as introductory, we See Trans. Camb. Phil. Soc. vol. xvi. pt. iv. Pr. 262–290. proceed to givo some typical examples of the method. Take a lattice of m columns and n rows, and consider the problem of

AUTHORITIES. — MACMAHON. “ Combinatory Analysis: A placing units in the compartments in such wise that the sth

Review of the Present State of Knowledge,Proceedings London column shall contain 1g units (s=1, 2, 3,... m), and the tth row

Mathematical Society, vol. xxviii. London, 1897. Here will be pe units (t=1, 2, 3,... n).

found a bibliography of the Theory of Partitions.—WHITWORTH. Writing

Choice and Chance.—LUCAS. Théorie des Nombres. Paris, 1891.

-CAYLEY. Collected Mathematical Papers, Cambridge, 1898, vol. 1+ajx + a2d2+ ... +...=(1+212)(1+a-x)(1+az2)...

ii. p. 419 ; vol. iii. pp. 36, 37; vol. iv. pp. 166-70 ; vol. v. Pp.

62–65, volp. ; vol. . pp. ; . x. 16, P

273–74 ; vol. xiii. pp. 47, 93-113, 269.—SYLVESTER. American bolic, so that D, is an operator of order p, the function is Journal of Mathematics, vol. v. pp. 119, 251.- MACMAHON. A4,94,913 ... am

Proceedings London Mathematical Society, vol. xix. p. 228 et seq. ;

Phil. Trans. Royal Society of London, vol. clxxxiv. pp. 835–901 ; and the operator Dp, Dp, Dpg ... Dpm The number

vol. clxxxv. pp. 111-60 ; vol. clxxxvii. pp. 619-73 ; vol. cxcii. Dp, Pp2 ... Dpyax, Q1,013 ... Aam enumerates the solutions. For the

pp. 351-401 ; Trans, Camb. Phil. Soc. vol. xvi. pp. 262–90.

(P. A. M.) mode of operation of D, upon a product reference must be made to the section on “Differential Operators” in the article ALGE Comets.-All comets move in orbits that are conic BRAIC FORMS. Writing

sections—ellipses, parabolas, or hyperbolas. The periodic Рn

comets move in elliptic orbits, and are usually seen at more aza, ...am + AΣα α

than one return. Non-periodic comets move in parabolas or, in partition notation,

(or in hyperbolas), and are seen at only one return. The

comets of each calendar year are provisionally designated (1^2)(1^2)...(19m)=... +A(P.P.-Pn)... +,

as 1895 A, 1895 B, 1895 C, &c., the letters A, B, C, &c. Dp, Pp,...Dpu(111)(112)... (11m)=A,

indicating the order of discovery. The name of the dis

or say

[merged small][ocr errors][subsumed][merged small][ocr errors][merged small][merged small][ocr errors][merged small]

and Dr= 5/(02, +azdag + azồag t...), the multiplication being sym-35, 611 ; vol. xi. pp. 61, 62, 357-64, 689–91 ; vol. xii. Pp. 217–19

[blocks in formation]
« EelmineJätka »