Many results on partitions can be obtained by the use of Ferrers’ diagram. The diagram of a partition is obtained by putting down a row of squares equal in number to the largest part, then immediately below it a row of squares equal in number to the next part, and so on. Such a diagram for 14 = 5 + 3 + 3 + 2 + 1 is shown in Figure 1.

By rotating the Ferrers’ diagram of the partition about the diagonal, it is possible to obtain from the partition n = x₁ + x₂ +⋯+ x_k the conjugate partition n = x₁* + x₂* +⋯x_n*, in which x_i* is the number of parts in the original partition of cardinality i or more. Thus the conjugate of the partition of 14 already given is 14 = 5 + 4 + 3 + 1 + 1. Hence, the following result is obtained:

(F₁) The number of partitions of n into k parts is equal to the number of partitions of n with k as the largest part.

Other results obtainable by using Ferrers’ diagrams are:

(F₂) The number of self-conjugate partitions of n equals the number of partitions of n with all parts unequal and odd.

Britannica Quiz

Numbers and Mathematics

(F₃) the number of partitions of n into unequal parts is equal to the number of partitions of n into odd parts.

Generating functions can be used with advantage to study partitions. For example, it can be proved that:

(G₁) The generating function F₁(x) of P(n), the number of partitions of the integer n, is a product of reciprocals of terms of the type (1 − x^k), for all positive integers k, with the convention that P(0) = 1

.

(G₂) The generating function F₂(x) of the number of partitions of n into unequal parts is a product of terms like (1 + x^k), for all positive integers k

.

(G₃) The generating function F₃(x) of the number of partitions of x consisting only of odd parts is a product of reciprocals of terms of the type (1 − x^k), for all positive odd integers k

.

Thus to prove (F₃) it is necessary only to show that the generating functions described in (G₂) and (G₃) are equal. This method was used by Euler.

The principle of inclusion and exclusion: derangements

For a case in which there are N objects and n properties A₁, A₂, · · · A_n, the number N(A₁, A₂), for example, will be the number of objects that possess the properties A₁, A₂. If N(Ā₁, Ā₂, · · ·, Ā_n) is the number of objects possessing none of the properties A₁, A₂, · · ·, A_n, then this number can be computed as an alternating sum of sums involving the numbers of objects that possess the properties

This is the principle of inclusion and exclusion expressed by Sylvester.

The permutation of n elements that displaces each object is called a derangement. The permutations themselves may be the objects and the property i may be the property that a permutation does not displace the ith element. In such a case, N = n! and N(A₁, A₂) = (n − 2)!, for example. Hence the number D_n of derangements can be shown to be approximated by n!/e

This number was first obtained by Euler. If n persons check their hats in a restaurant and if the waiter loses the checks and returns the hats at random, the chance that no one receives his own hat is D_n/n! = e⁻¹ approximately. It is surprising that the approximate answer is independent of n. To six places of decimals, e⁻¹ = 0.367879. When n = 6, the error of approximation is less than 0.0002.

If n is expressed as the product of powers of its prime factors p₁, p₂,…p_k, and if the objects are the integers less than or equal to n, and if A_i is the property of being divisible by p_i, then Sylvester’s formula gives, as the number of integers less than n and prime to it, a function of n, written ϕ(n), composed of a product of n and k factors of the type (1 − 1/p_i)

.

The function ϕ(n) is the Euler function.

Polya’s theorem

It is required to make a necklace of n beads out of an infinite supply of beads of k different colours. The number of different necklaces, c (n, k), that can be made is given by the reciprocal of n times a sum of terms of the type ϕ(n) k^n/d, in which the summation is over all divisors d of n and ϕ is the Euler function

.

Though the problem of the necklaces appears to be frivolous, the formula given above can be used to solve a difficult problem in the theory of Lie algebras, of some importance in modern physics.

The general problem of which the necklace problem is a special case was solved by the Hungarian-born U.S. mathematician George Polya in a famous 1937 memoir in which he established connections between groups, graphs, and chemical bonds. It has been applied to enumeration problems in physics, chemistry, and mathematics.

The Möbius inversion theorem

In 1832 the German astronomer and mathematician August Ferdinand Möbius proved that, if f and g are functions defined on the set of positive integers, such that f evaluated at x is a sum of values of g evaluated at divisors of x, then inversely g at x can be evaluated as a sum involving f evaluated at divisors of x

In 1964 the U.S. mathematician Gian-Carlo Rota obtained a powerful generalization of this theorem, providing a fundamental unifying principle of enumeration. One consequence of Rota’s theorem is the following:

If f and g are functions defined on subsets of a finite set A, such that f(A) is a sum of terms g(S), in which S is a subset of A, then g(A) can be expressed in terms of f

Special problems

Despite the general methods of enumeration already described, there are many problems in which they do not apply and which therefore require special treatment. Two of these are described below, and others will be met further in this article.