Page:EB1911 - Volume 06.djvu/775

This page has been proofread, but needs to be validated.

COMBINATORIAL ANALYSIS

753

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 objects be not all similar they cannot be effectively enumerated Fundamental problem. 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 p₁ of one kind, q₁ of a second, r₁ of a third, &c., where p₁ + q₁ + r₁ + . . . = m. We may thus denote the classes either by the multipartite numbers ________
p₁q₁r₁ . . ., or by the partition (p₁q₁r₁ . . . ) 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₁q₁r₁ . . . ) 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

xⁿ − a₁xⁿ⁻¹ + a₂xⁿ⁻² − . . . = 0

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

ΣA_{(pqr. . .), (p₁q₁r₁...)} · (pqr. . .),

where the numbers p₁, q₁, r₁ . . . 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₁q₁r₁ . . . ). 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 the quantities α, β, γ, . . . so Case I.that

(1 − αx. 1 − βx. 1 − γx. ...)⁻¹ = 1 + h₁x + h₂x² + h₃x³ + ...

h₁ = Σα = (1)
h₂ = Σα² + Σαβ = (2) + (1²)
h₃ = Σα³ + Σα²β + Σαβγ = (3) + (21) + (1³).

Form the product h_p₁h_q₁h_r₁...

Any term in h_p₁ may be regarded as derived from p₁ objects distributed into p₁ 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₁ letters from the letters in α^pβ^qγ^r . . . will occur in some term of h_p₁, every further selection of q₁ letters will occur in some term of h_q₁, and so on. Therefore in the product h_p₁h_q₁h_r₁ . . . 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₁q₁r₁ . . .) one object in each parcel. Hence

ΣA_{(pqr . . .), (p₁q₁r₁ . . .)} · (pqr . . .)＝h_p₁h_q₁h_r₁ ....

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₁q₁r₁ . . .) and the distribution of objects (p₁q₁r₁ . . .) 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_p₁h_q₁h_r₁ . . . is equal to the coefficient of symmetric function (p₁q₁r₁ . . .) in the development of the product h_ph_qh_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₁, a₂, a₃, . . . or (1), (1²), (1³), . . . in lieu of the quantities h₁, h₂, h₃, . . . The distribution function has then the value a_p₁a_q₁a_r₁... or (1^p₁) (1^q₁) (1^r₁) ..., 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_p₁a_q₁a_r₁ . . . in a series of monomial symmetric functions, is equal to the coefficient of the function (p₁q₁r₁ . . .) in the similar development of the product a_pa_qa_r . . . .

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

Write

X₁ = (1)x₁,
X₂ = (2)x₂ + (1²)x2
1,
X₃ = (3)x₃ + (21)x₂x₁ + (1³)x3
1

.......

and generally

X_s = Σ(λμν ...) x_λ x_μ x_ν . . .

⁠

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

X_p₁X_q₁X_r₁ ... = ΣP $x_{s_{1}}^{\sigma _{1}}x_{s_{2}}^{\sigma _{2}}x_{s_{3}}^{\sigma _{3}}...$

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

Definition I.—Of a number n take any partition (λ₁λ₂λ₃ . . . λ_s) and separate it into component partitions thus:—

(λ₁λ₂) (λ₃λ₄λ₅) (λ₆)...

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—

Σα^λ₁β^λ₂Σα^λ₃β^λ₄γ^λ₅Σα^λ₆...

The portions (λ₁λ₂), (λ₃λ₄λ₅), (λ₆), . . . are termed separates, and if λ₁ + λ₂ = p₁, λ₃ + λ₄ + λ₅ = q₁, λ₆ = r₁. . . be in descending order of magnitude, the usual arrangement, the separation is said to have a species denoted by the partition (p₁q₁r₁ ...) 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 ξ₁, ξ₂, ξ₃,. . ., where (ξ₁, ξ₂, ξ₃. . .) is some partition of n. The distribution is then said to have a specification denoted by the partition (ξ₁ξ₂ξ₃. . .).

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 ${\big (}s_{1}^{\sigma _{1}}s_{2}^{\sigma _{2}}s_{3}^{\sigma _{3}}...{\big )}$ of species (p₁q₁r₁. . .). Further, P is the distribution function of objects into parcels denoted by (p₁q₁r₁. . .), subject to the restriction that the distributions have each of them the specification