Open main menu
This page has been proofread, but needs to be validated.
753
COMBINATORIAL ANALYSIS

The most important problem of combinatorial analysis is connected with the distribution of objects into classes. A number n may be regarded as enumerating n similar objects; it is then said to be unipartite. On the other hand, if the Funda-
mental problem.
objects be not all similar they cannot be effectively enumerated by a single integer; we require a succession of integers. If the objects be p in number of one kind, q of a second kind, r of a third, &c., the enumeration is given by the succession pqr . . . which is termed a multipartite number, and written,

pqr . . . ,

where p+q+r+ . . . = n. If the order of magnitude of the numbers p, q, r, . . . is immaterial, it is usual to write them in descending order of magnitude, and the succession may then be termed a partition of the number n, and is written (pqr . . .). The succession of integers thus has a twofold signification: (i.) as a multipartite number it may enumerate objects of different kinds; (ii.) it may be viewed as a partitionment into separate parts of a unipartite number. We may say either that the objects are represented by the multipartite number pqr . . ., or that they are defined by the partition (pqr . . . ) of the unipartite number n. Similarly the classes into which they are distributed may be m in number all similar; or they may be p1 of one kind, q1 of a second, r1 of a third, &c., where p1 + q1 + r1 + ... = m. We may thus denote the classes either by the multipartite numbers ________
p1q1r1 . . .
, or by the partition (p1q1r1 . . . ) of the unipartite number m. The distributions to be considered are such that any number of objects may be in any one class subject to the restriction that no class is empty. Two cases arise. If the order of the objects in a particular class is immaterial, the class is termed a parcel; if the order is material, the class is termed a group. The distribution into parcels is alone considered here, and the main problem is the enumeration of the distributions of objects defined by the partition (pqr . . .) of the number n into parcels defined by the partition (p1q1r1 . . . ) of the number m. (See “Symmetric Functions and the Theory of Distributions,” Proc. London Mathematical Society, vol. xix.) Three particular cases are of great importance. Case I. is the “one-to-one distribution,” in which the number of parcels is equal to the number of objects, and one object is distributed in each parcel. Case II. is that in which the parcels are all different, being defined by the partition (1111...), conveniently written (1m); this is the theory of the compositions of unipartite and multipartite numbers. Case III. is that in which the parcels are all similar, being defined by the partition (m); this is the theory of the partitions of unipartite and multipartite numbers. Previous to discussing these in detail, it is necessary to describe the method of symmetric functions which will be largely utilized.

Let α, β, γ, . . . be the roots of the equation

xn − a1xn−1 + a2xn−2 − . . . = 0

The symmetric function Σαpβqγr..., where p + q + r + ... = n is, in the partition notation, written (pqr . . .). Let A(pqr...), (p1q1r1...) denote the number of ways of distributing The distribution function. the n objects defined by the partition (pqr . . .) into the m parcels defined by the partition (p1q1r1 . . . ). The expression

ΣA(pqr. . .), (p1q1r1...) · (pqr. . .),

where the numbers p1, q1, r1 ... are fixed and assumed to be in descending order of magnitude, the summation being for every partition (pqr. . .) of the number n, is defined to be the distribution function of the objects defined by (pqr. . .) into the parcels defined by (p1q1r1 . . . ). It gives a complete enumeration of n objects of whatever species into parcels of the given species.

1. One-to-One Distribution. Parcels m in number (i.e. m = n).—Let hs be the homogeneous product-sum of degree s of Case I. the quantities α, β, γ, . . . so that

(1 − αx. 1 − βx. 1 − γx. ...)−1 = 1 + h1x + h2x² + h3x³ + ...

h1 = Σα = (1)
h2 = Σα² + Σαβ = (2) + (1²)
h3 = Σα³ + Σα²β + Σαβγ = (3) + (21) + (1³).

Form the product hp1hq1hr1...

Any term in hp1 may be regarded as derived from p1 objects distributed into p1 similar parcels, one object in each parcel, since the order of occurrence of the letters α, β, γ, ... in any term is immaterial. Moreover, every selection of p1 letters from the letters in αpβqγr . . . will occur in some term of hp1, every further selection of q1 letters will occur in some term of hq1, and so on. Therefore in the product hp1hq1hr1 ... the term αpβqγr ..., and therefore also the symmetric function (pqr . . . ), will occur as many times as it is possible to distribute objects defined by (pqr . . .) into parcels defined by (p1q1r1 ...) one object in each parcel. Hence

ΣA(pqr . . .), (p1q1r1 . . .) · (pqr . . .) = hp1hq1hr1 ....

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

A A A A A B B
a a a a b b b

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.:—

A A A A B B B
a a a a a b b.

The process is clearly of general application, and establishes a one-to-one correspondence between the distribution of objects (pqr . . .) into parcels (p1q1r1 . . .) and the distribution of objects (p1q1r1 . . .) 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 hp1hq1hr1 . . . is equal to the coefficient of symmetric function (p1q1r1 . . .) in the development of the product hphqhr ....”

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 a1, a2, a3, . . . or (1), (1²), (1³), . . . in lieu of the quantities h1, h2, h3, . . . The distribution function has then the value ap1aq1ar1... or (1p1) (1q1) (1r1) ..., 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 ap1aq1ar1 . . . in a series of monomial symmetric functions, is equal to the coefficient of the function (p1q1r1 . . .) in the similar development of the product apaqar . . . .

The general result of Case I. may be further analysed with important consequences.

Write

X1 = (1)x1,
X2 = (2)x2 + (1²)x2
1
,
X3 = (3)x3 + (21)x2x1 + (1³)x3
1

.......

and generally

Xs = Σ(λμν ...) xλ xμ xν ...

the summation being in regard to every partition of s. Consider the result of the multiplication—

Xp1Xq1Xr1 ... = ΣPxσ1
s1
xσ2
s2
xσ3
s3
...

To determine the nature of the symmetric function P a few definitions are necessary.

Definition I.—Of a number n take any partition (λ1λ2λ3 . . . λs) and separate it into component partitions thus:—

(λ1λ2) (λ3λ4λ5) (λ6)...

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—

Σαλ1 βλ2 Σαλ3 βλ4 γλ5 Σαλ6...

The portions (λ1λ2), (λ3λ4λ5), (λ6), . . . are termed separates, and if λ1 + λ2 = p1, λ3 + λ4 + λ5 = q1, λ6 = r1. . . be in descending order of magnitude, the usual arrangement, the separation is said to have a species denoted by the partition (p1q1r1 ...) 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 ξ, whenever we observe ξ similar objects in similar parcels we will obtain a succession of numbers ξ1, ξ2, ξ3, . . ., where (ξ1, ξ2, ξ3. . .) is some partition of n. The distribution is then said to have a specification denoted by the partition (ξ1ξ2ξ3 . . .).

Now it is clear that P consists of an aggregate of terms, each of which, to a numerical factor près, is a separation of the partition (sσ1
1
sσ2
2
sσ3
3
...) of species (p1q1r1 . . .). Further, P is the distribution function of objects into parcels denoted by p1q1r1 . . .), subject to the restriction that the distributions have each of them the specification