EA (psr...), (p, „...)• (pqr...)  =hP1h41hr1 .... This theorem is of algebraic importance; for consider the simple particular case of the distribution of objects (43) into parcels (52), and represent objects and parcels by small and capital letters respectively . One distribution is shown by the scheme AAAAABB aaaabbb wherein an object denoted by a small letter is placed in a parcel denoted by the capital letter immediately above it . We may interchange small and capital letters and derive from it a distribution of objects (52) into parcels (43); viz.: AAAABBB aaaaabb' The process is clearly of general application, and establishes a one-to-one correspondence between the distribution of objects (pqr ... ) into parcels (pigir1 . . .) and the distribution of objects (pigiri . ) into parcels (pqr . ) . It is in fact, in Case I., an intuitive observation that we may either consider an object placed in or attached to a parcel, or a parcel placed in or attached to an object . Analytically we have Theorem.—” The coefficient of symmetric function (pqr .) in the development of the product h51h91hr1... is equal to the coefficient of symmetric function (plgirl ..) in the development of the product hphghr .... The problem of Case I. may be considered when the distributions are subject to various restrictions . If the restriction be to the effect that an aggregate of similar parcels is not to contain more than one object of a kind, we have clearly to deal with the elementary symmetric functions al, a2, a3, .

. or (1), (12), (13), .. in lieu of the quantities hi, h2, ha, ... The distribution function has then the value apjasiar1... or (1si) (14,) (1'1)..., and by interchange of object and parcel we arrive at the well-known theorem of symmetry in symmetric functions, which states that the coefficient of symmetric function (pqr . . .) in the development of the product a 1a51a,1... in a

series of monomial symmetric functions, is equal to the coefficient of the function (pigiri .) in the similar development of the product ayagar ... . The general result of Case I. may be further analysed with important consequences . Write Xi = (1)xi, X2=(2)x2+(12)x,, X3 = (3)x3+(21)x2x1+(13)x and generally X, =E(7iµy ...)xxxµxy ... the summation being in regard to every partition of s . Consider the result of the multiplication X3,X4,Xr, ... = EPx 31xa2x sae . To determine the nature of the symmetric f unction P a few definitions are necessary . Definition I.—Of a number n take any partition (X3X2X3 . . . X3) and separate it into component partitions thus: (X1T2) (A3x4x5) (A6).•• in any manner .

This may be termed a separation of the partition, the

numbers occurring in the separation being identical with those which occur in the partition . In the theory of symmetric functions the separation denotes the product of symmetric functions F.aXle-EaX20x'ya5eaA ... The portions (X1X2), (X3X4X5), (A6), . are termed separates, and if X1+X2 =p1, X3+X4+X5 =q1, A6 =r1... be in descending order of magni- tude, the usual arrangement, the separation is said to have a species denoted by the partition (plain . . .) of the number n . Definition II.—If in any distribution of n objects into n parcels (one object in each parcel), we write down a number E, whenever we observe E similar objects in similar parcels we will obtain a succession of numbers y Si, ea, ea, ... , where (e1, Es, E3...) is some partition of n . The distribution is then said to have a specification denoted by the partition (EIE2E3 ... Now it is clear that P consists of an aggregate of terms, each of which, to a numerical factor pres, is a separation of the partition (sQis2s°33...) of species 1 2 (Agin...) . Further, P is the distribution function of objects into parcels denoted by (plgirl...) subject to the restriction that the distributions have each of them the specification The distribution function . Case I . Case H . (p1 2 3 "lp"2p"a) a partition of n .

Of the whole number of distributions of the n objects, there will be a certain number such that nl parcels each contain pi objects, and in general Ira parcels each contain pa objects, where s = I, 2, 3, .. Consider the product h"1h r2h"3... which can be permuted in P1 P2 P3 m! ways . For each of these ways h'1 h"2h"a... will be a dis- 7rl ! 7r2 ! 7r3!••• P1 P2 P3 tribution function for distributions of the specified type . Hence, regarding all the permutations, the distribution function is m! h"1h"2h"a 7r1!

r2 . 7r3 !... P1 P2 P3 ••• and regarding, as well, all the partitions of n into exactly m parts, the desired distribution function is m, h lh 2h a 7r1 ! 7r2! ital ... PI P2 P3"' {171'=m, 17rp=nj, that is, it is the coefficient of xn in (hlx+hzx2+hax3+...)m . The value of A(p"1p"2pa„.)(1m) is the coefficient of(pi1pz2p;3...)xn in 1 2 3 the development of the above expression, and is easily shown to have the value /pl+1n—1\ "l (p2+m—1)'r2 /p3+m—11 "3 ... Pi P2 Pa (m\ (pl+m -2\ "1 (p2+m—21 "2 (ps+m—21 "a \ 1 J l 1 ` P2 / '. p3 I (nz) (pl+m-3\ "1 (Ps +m-3) "2 (pa+m-31 "a + 2 p1 I \ P2 I ` Pa / -...to m terms.I Observe that when p1= Ps =Ps = ...

=7r1=7r2 =nos . . . = i this expression reduces to the mth divided

differences of on . The expression gives the compositions of the multipartite number pi1pa 2pa 8 ... into m parts . Summing the distribution function from m=I to m=oo and putting x=1, as we may without detriment, we find that the totality of the compositions is given by 1 hlhh3hh h3 . which may be given the form a1-~+aa "' Adding 1 we bring 1-2(al -azd-a3-...) . this to the still more convenient form 1 11-2(al-az+as-...) . Let F(pilp22p33...)denote the total number of compositions of the multipartite pllp;2pe3 .... Then 11 120.=1+EF(p)al', and thence F(p) =2P-1 . Again 11_ +1 =1+EF(p1p2)aPl13m,andexpanding the left-hand side we easily find F(pip2) =2P1+P2—1(P1+P2) !—2PI+P2-2 (A1+p2—1) ! 0!p1!p3 ! 1!(p1-1)!(p2-1) ! +2P1+P2-32!03-2 !-a)!2)I- ....

We have found that the number of compositions of the multi-partite plpsp3...p. is equal to the coefficient of symmetric function (p1p2p3...p,) or of the single

term aP1a22a83...aP' in the development according to ascending powers of the algebraic fraction 1 1 1 — 2 (Mal - Zala2 +f ala2a3 — ... + (—) a+l0.lasa3 ... aa . This result can be thrown into another suggestive form, for it can be proved that this portion of the expanded fraction {1—il(2al+as+...+aa)} 11—is(Ya1+Las+••.+aa)}...{1—ta(Gal+2a2+...+2as) which is composed entirely of powers of t1a', t2a2, t3a3, ...taaa has the expression 3 . 2 1—2(2,11.1—Itlisalas+2611st3al.ana .. +(—)a+ltlts...tealas...aa), and therefore the coefficient of a 2a21 .aP' in the latter fraction, when tl, t2, &c., are put equal to unity, is equal to the coefficient of the same term in the product 1 (gal+a3+...+aa)Pl(2a1+2a2+...+as)P2...(2a1+2a2+...+2aa)Pe . This result gives a direct connexion between the number of compositions and the permutations of the letters in the product ai'1a2P2...aPe . Selecting any permutation, suppose that the letter a,. occurs q,. times in the last p,+p.+1+•••+pa places of the permutation; the co-efficient in question may be represented by 1E20-+q2+...+qa the summation being for every permutation, and since q1= p1 this may be written 2 P l—1 E 2 g2+q 3+...+q a . Ex . Gr.—For the bipartite z2, pl = p2 2, and we have the following scheme: a2 a2 q2 = 2 al as = 1 as al = 1 al as = 1 . as al = 1 a2 a3 al al =0 Hence F(22) =2(22+2+2+2+2+2°) =26 . We may regard the fraction 1 i !

• {1—11(2.1+a2+...+ae)} {1—12(2.1+'Las+...+ae)} ... {1—1.(22.1+2.2+ .. ±2a.) as a redundant generating function, the enumeration of the compositions being given by the coefficient of (t, al) P1(tact) P2 ... (tacts) Ps . The transformation of the pure generating function into a factorized redundant form supplies the

key to the solution of a large number of questions in the theory of ordinary permutations, as will be seen later . [The transformation of the last section involves The theory a comprehensive theory of Permutations, which it is ofpermuconvenient to discuss shortly here. rations . If X1, X2, X3, ... Xn be linear functions given by the matricular relation (X1, X2, ••• Xn = (a11 a12 ... a1n) (x1, x2, ...xn) a21 a22 ... a2n and ant ... ann that portion of the algebraic fraction, 1 (1 —s1X1) (1 —s2X2) ... (1 —$nXn) ' which is a function of the products s1x1, s2x2, S3x3...s,,xn only 'is 1 1(1 — allsixl) (1 —a22s2x2) (1 —a33s3x3) ... (1 —annSnxn) ( I where the denominator is in a symbolic form and denotes on expansion 1- 2I au I s1 x1 + Z Ian (122 1 s1 szxlx2- ... + (-) n I aua22a33... an n I slsz... snxl xz... xn, where lank 1aua22l,...lana22,...annl denote the several co-axial minors of the determinant ana22...annl of the matrix . (For the proof of this theorem see MacMahon, " A certain Class of Generating Functions in the Theory of Numbers," Phil .

Trans . R . S. vol. clxxxv . A, 1894) . It follows that the co-efficient of xel e2 1 2 denoted by the partition @a', 1.1242...) .