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,
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
p_{1} of one kind, q_{1} of a second, r_{1} of a third, &c., where
p_{1} + q_{1} + r_{1} + ... = m. We may thus denote the classes either
by the multipartite numbers ________
p_{1}q_{1}r_{1} . . ., or by the partition
(p_{1}q_{1}r_{1} . . . ) 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 (p_{1}q_{1}r_{1} . . . )
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
(1^{m}); 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
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 (p_{1}q_{1}r_{1} . . . ). The expression
where the numbers p_{1}, q_{1}, r_{1} ... 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 (p_{1}q_{1}r_{1} . . . ). 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 h_{s} be the homogeneous product-sum of degree s of Case I. the quantities α, β, γ, . . . so that
(1 − αx. 1 − βx. 1 − γx. ...)^{−1} = 1 + h_{1}x + h_{2}x² + h_{3}x³ + ...
h_{1} = Σα = (1) |
Form the product h_{p1}h_{q1}h_{r1}...
Any term in h_{p1} may be regarded as derived from p_{1} objects distributed into p_{1} similar parcels, one object in each parcel, since the order of occurrence of the letters α, β, γ, ... in any term is immaterial. Moreover, every selection of p_{1} letters from the letters in α^{p}β^{q}γ^{r} . . . will occur in some term of h_{p1}, every further selection of q_{1} letters will occur in some term of h_{q1}, and so on. Therefore in the product h_{p1}h_{q1}h_{r1} ... 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 (p_{1}q_{1}r_{1} ...) one object in each parcel. Hence
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 (p_{1}q_{1}r_{1} . . .) and the distribution of objects (p_{1}q_{1}r_{1} . . .) 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 h_{p1}h_{q1}h_{r1} . . . is equal to the coefficient of symmetric function (p_{1}q_{1}r_{1} . . .) in the development of the product h_{p}h_{q}h_{r} ....”
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 a_{1}, a_{2}, a_{3}, . . . or (1), (1²), (1³), . . . in lieu of the quantities h_{1}, h_{2}, h_{3}, . . . The distribution function has then the value a_{p1}a_{q1}a_{r1}... or (1^{p}_{1}) (1^{q}_{1}) (1^{r}_{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_{p1}a_{q1}a_{r1} . . . in a series of monomial symmetric functions, is equal to the coefficient of the function (p_{1}q_{1}r_{1} . . .) in the similar development of the product a_{p}a_{q}a_{r} . . . .
The general result of Case I. may be further analysed with important consequences.
Write
X_{1} = (1)x_{1}, |
and generally
X_{s} = Σ(λμν ...) x_{λ} x_{μ} x_{ν} ...
the summation being in regard to every partition of s. Consider the result of the multiplication—
s_{1} xσ_{2}
s_{2} xσ_{3}
s_{3} ...
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} = p_{1}, λ_{3} + λ_{4} + λ_{5} = q_{1}, λ_{6} = r_{1}. . . be in descending order of magnitude, the usual arrangement, the separation is said to have a species denoted by the partition (p_{1}q_{1}r_{1} ...) 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 (p_{1}q_{1}r_{1} . . .). Further, P is the distribution function of objects into parcels denoted by p_{1}q_{1}r_{1} . . .), subject to the restriction that the distributions have each of them the specification