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 onetoone 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 wellknown 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.aXleEaX20x'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+m3\ "1 (Ps +m3) "2 (pa+m31 "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
12(al azda3...).
this to the still more convenient form
1
112(alaz+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) =2P1. Again 11_ +1 =1+EF(p1p2)aPl13m,andexpanding the lefthand side we easily find
F(pip2) =2P1+P2—1(P1+P2) !—2PI+P22 (A1+p2—1)!
0!p1!p3! 1!(p11)!(p21)! +2P1+P232!032 !a)!2)I....
We have found that the number of compositions of the multipartite 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 coefficient 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 coaxial 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 coefficient of
xel e2
1 2
denoted by the partition @a', 1.1242...). Employing a more general notation we may write
End of Article: EA (psr...), (p, „...)• (pqr...) 

[back] EA (nar...), (p.s„,.,.) 
[next] EABANI 
There are no comments yet for this article.
Do not copy, download, transfer, or otherwise replicate the site content in whole or in part.
Links to articles and home page are encouraged.