COMBINATORIAL Let (7r1 tt2 7r3 ...) be a partition of m a partition of n. Of the whole number of distributions of the n objects, there will be a certain number such that 7r1 parcels each contain pi objects, and in general irs parcels each contain ps objects where s=l.’ 2,’ 3 ’ Consider the *product ri P2 Ps ... which can be m! ways. For each of these ways permuted in Case II.
ANALYSIS
155
when tv t2, &c., are put equal to unity, is equal to the coefficient of the same term in the product J‘s.
(2a1+a2+ ... +a,p(2ai+2a2+ ... +asf2... (2ai+2a2+ ... +2a»f
This result gives a direct connexion between the number of compositions and the permutations of the letters in the product a^1^’2 ... a3s. Selecting any permutation, suppose that the letter ar occurs qr times in the last pr+pr+i+ ... +Pj places of the permutation ; the coefficient in question may be represented by £223l+32+-"+3,s, the summation being for every permutation, and since g'i=Pi this may be1 written 2Pi - 2222+?3'h" +2*. Ex. Gr.—For the bipartite 22 ,pi=p2=2, and we have the following scheme :— 0,! ttj a2 a2 9,2 = 2 di a2 «i a2 = 1 ai 0-2 a2 cq = 1 a2 cq aL a2 = 1 =1 a2 aj a2 a3 =0 a2 a2 cq tti 2 Hence F(22) = 2(2 + 2 + 2 + 2 + 2 + 20)=:26. We may regard the fraction
h^h^h 3... will be a distribution function for distributions of Pi Pa Ps the specified type. Hence, regarding all the permutations, the distribution function is 771 ! 7ti 7T2 nj TTj !7r2 !7r3 !... ^PilpJL'Pa and regarding, as well, all the partitions of n into exactly m parts, the desired distribution function is 3 m! ['Lir = m, ’Livp — n'], TTi ! 7r2 ! TTj ! -A’W . Pi Pa Pa. n that is, it is the coefficient of x in (hix + Jirpa2 + + ... )ra. The value of A . _ is the coefficient of {p?PaP?--y ) in the development of the above expression, and is easily shown i • {1 ~ h(2ai-Hao-K.• +a )j. |1- < (2ai+2a +... +a )|... jl - L(2ai+2a2+...+2a )js 2 2 4 J to have the value as a redundant generating function, the enumeration of the 1 r2 ^p1 + m-l^ ^p2 + 7n-j ' (pz+m-l compositions being given by the coefficient of (t1a^Pl(t2a2)n ... (tsas)Ps. ^m^Pi + m-2^ 1^P2 + m - 2^ + The transformation of the pure ge-nerating 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 jf,e0Cy — ... to to terms. Observe that when p1=p2=p3=... =7r1 = 7r2 = ’7r3=... =1 this ex- a comprehensive theory of Permutations, which of Permit= tations. pression reduces to the with divided difference of 0”. The expression it is convenient to discuss shortly here. If Xj, X2, X-j, ... Xn be linear functions given by the matricular gives the compositions of the multipartite number • • relation into to parts. Summing the distribution function from to = 1 to (Xi, X2, ... X„)= ( <hl «12 — «i«) (*1, ®2> - xn) 77i—ao and putting x=l, as we may without detriment, we find ^21 ^22 * * * ^271 ... . . 1 hi + A + h + ... that the totality of the compositions is given by 1 _ ^ 2 3 _— which may be given the form pY2(a
—)’
h we
that portion of the algebraic fraction 1 bring this to the still more convenient form (1 - SiXjXl — s2X2) ... (1 - snA„)’ x2 1 - 2(a1-a2 + a3 - ...) which is a function of the products s^i, s2x2, ssxs ... snxn only is Let F^^p^Ps3---) denote the total number of compositions of = +2 1(1 - OllSl«l)(l - a^S-E2)(l - a33S3xs) (!- annSnXn) | Then F(p)aP, and the multipartite 2a 4 where the denominator is in a symbolic form and denotes on expansion thence F(p) = 2p-i. Again +(i-afi)= ^ + 2F(^iP2)aPl/3C2, 1 - 21 an I si*i+2|aiia22| sis^^ I aiia22a33... a„n ls1s2...s„z1x2...Xn, and expanding the left-hand side we easily find where |aul, Ki^l, - l«n«22 - a»nl denote the several co-axial minors of the determinant ! Pl+P2 2 ( I+ 1) ! FC n n2)-2 l - 2Pl+I>2 “1 0(ffi+ffa) “ 1!)/(pj-1)! ^ 1?,7(P2-1) 1M! F(PiP !Pi!p2 ! _ 2^
- * * ^"nn I
(Pi +Pa ~ 2)! ^ 2 ! (pi-2) ! (p2-2)! -• We have found that the number of compositions of the multipartite PiPaPs..-Ps is equal to the coefficient of symmetric tunction (PiP2p3 ...ps) or of the single term a^aJ^a1^'... aPs in the development according to ascending powers of the algebraic fraction +, <jPi+Pa - 3
2 ' 1 - 2(2ai - 2aia2 + Scqa^ -... + (- )s+1aiaaa3 • • • as This result can be thrown into another suggestive form, for it can be proved that that portion of the expanded fraction 2
• |1 - ti(2ai-t-a2+...+a,)} {1 - to(2ai+2a2+...+a4)}... {1 - f4(2ai+‘2a2+...+2as)} ’ which is composed entirely of powers of t'80'8 has the expression ■ 1 -2(2«iai -3,tit2a1ai+1ht2t-io.1*2a2-•••+(->5+hp2...Laia2...as) and therefore the coefficient of a^a^1... a3s in the latter fraction,
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 coefficient of in the product {allxl+al2x2+..pclranfHaairi+o-a^a+..+^nXnf1..{o^1x1po.nax2+..+annXn)^ is equal to the coefficient of the same term in the expansion ascending-wise of the fraction ^ 1 - S | an | xi + S | ana22| aqaq -...+(- )”1 «na22- • • a«» I xixf ■ -Xn If the elements of the determinant be all ot them equal to unity, we obtain the functions which enumerate the unrestricted permutations of the letters in
x:/ 1x*£2 ■■■xin > n
2
and
(x1 + x2+ ...+x„) fl+f2+---+^ 1 1 — (aq + a:2 + ... + xn)
