Counting partitions

(notes by R. Bigoni)


1. Partition of a set

A finite set S with n elements can be subdivided into k parts pi such that

Each of these possible subdivisions is said a partition of S.

 


2. Stirling numbers of the second kind

If the elements of S are all distinguishable, the number of its partitions in k parts (or k-partitions) is represented by the symbol Eqn001.gif, proposed by the Serbian mathematician Jovan Karamata in analogy with the symbol used for the binomial coefficients, id said Stirling number of the second kind, named after the Scottish mathematician J. Stirling

Given n, the following identities are immediate:

If n > 1 and s is one of the elements of S, the k-partitions of S may be of two kinds:

Let C be the complementary of {s} with respect to S.

The partitions of kind X are Eqn105.gif because every (k-1)-partition of C united with the singleton {s} forms a k-partition of S.

The partitions of kind Y are Eqn106.gif, because every k-partition of C united with the singleton {s} forms a k-partition of S.

Assuming

Eqn104_1.gif

one gets

Eqn104.gif

For n>1, the equation (1,1) allows to derive recursively the Stirling numbers of the second kind.

The following Javascript application allows to calculate the Stirling numbers of the second kind (big numbers may require a lot of computing time).

 

 

For big numbers you can use WolframAlpha.

fig002.png

Writing the Stirling numbers in successive rows with increasing n and k, we get the triangle of Stirling.

Eqn109.gif

 


2. Grunert's polynomials

We can directly obtain the values of Eqn001.gif using the Grunert's polynomials. Given a continuous function f(x), we define the operator G such that

Eqn110.gif

If f(x)=ex, we have

Eqn111.gif

Successive applications of G to the results of the previous applications give

Eqn112.gif

The polynomials that multiply the exponential function are the Grunert's polynomials.

We observe that the coefficients of the Grunert's polynomials coincide with the Stirling numbers of the second kind. This is not accidental because they are formed in the same recursive way. In fact, if we represent with gnk the coefficients of the polynomial of Gn, we have

Eqn113.gif

Eqn114.gif

then

Eqn115.gif

The formation of the coefficients gn,k coincides with the equation (1.1), then

Eqn116.gif

If now we repeatedly apply the operator G to the expansion in Maclaurin series of the natural exponential function Eqn117.gif we get

Eqn118.gif

By equating the two expressions of Gn, we get

Eqn119.gif

Eqn120.gif

Eqn121.gif

Eqn122.gif

Eqn123.gif

The sum at the right side is a sum on the growing powers of x with exponents l+j. Since the sum at the left side if finite, with k from 0 to n, we assume

Eqn124.gif

then

Eqn125.gif

Eqn126.gif

Eqn127.gif

Eqn128.gif

By comparing the sums at both sides, we get

Eqn129.gif

This equation connects the Stirling numbers of the second kind with the binomial coefficients and allows a faster calculation.

Since Eqn101.gif, from (1.2) we get

Eqn131.gif

By multiplying both the sides of (1.3) by (-1)n

Eqn132.gif

The power (-1)2n-j are identical to powers (-1)j, then

Eqn133.gif

To know more

 


3. Bell numbers

If the n elements of S are all distinguishable, the number of its partitions is given by the sum of all the Stirling numbers of the second kind with k from 1 to n. This number is known as Bell number Bn, named after the mathematician and novelist E. T. Bell.

Eqn140.gif

The Bell numbers can be recursively obtained with the following procedure

Eqn141.gif

that is

In this way we can build the Bell triangle.

Eqn142.gif

The numbers in the first column are the Bell numbers.

The following Javascript application allows to obtain the Bell numbers (big numbers may require a lot of computing time).

 

 

For big numbers you can use WolframAlpha®.

fig003.png

 


4. Partition function

If the n elements of a set S are all indistinguishable from one another, the number of its partitions is drastically reduced compared to that calculated by the Bell number.

In fact, if, for example, we consider the set I = {a,b,c,d}, the number of its partitions is B4 = 15, but if we consider the set S = {a,a,a,a}, we can extract from it the following partitions:

then the number of its partitions is 5.

The calculation of the number of partitions of a set of n indistinguishable elements coincides with the calculation of the number of ways in which the natural number n can be written as a sum of positive natural summands ≤ n. So the term partition can be imported from set theory to that of the natural numbers.

Given a positive natural number n, we call partition Λn,k of n a non-decreasing sequence of positive natural numbers λn,in

Eqn021.gif

such that

Eqn002.gif

Obviously, the maximum value of k, that is, n, is obtained in the case in which all the λn,i are equal to 1.

It is obvious that the number 1 admits only the partition Eqn003.gif.

The number 2 admits two partitions:

Eqn004.gif

The number 3 admits three partitions:

Eqn005.gif

The number 4 admits five partitions:

Eqn006.gif

The number 5 admits seven partitions::

Eqn007.gif

Given any positive natural number n, the number p(n) of its possible partitions is given by the partition function.

From the proposed examples we get

 


5. Partition function and pentagonal numbers

As we can see in the bibliography of the cited page of Mathworld, several mathematicians have studied the properties of the partition function, in particular with the aim of identifying algorithms that allow the determination of its value for any argument n.

A first important result was the recursive formula of Euler, for which the values of p(n) are given by the values p(ni ) of all the numbers that are obtained by subtracting from n the generalized pentagonal numbers ωin. We assume p(0)=1.

The set Ω of generalized pentagonal numbers ωi is obtained from the union of sequences of natural numbers Eqn010.gif defined as follows

Eqn008.gif

 

 

If, for example, n=10, the numbers ni obtained by subtracting 10 from the generalized pentagonal numbers ωi ≤10 are:

 

The Euler's recursive formula states that, given the maximum index iM for the numbers ni

Eqn011.gif

where (i-1):2 represents the integer quotient of i-1 divided by 2.

In practice, in the sum two positive terms alternate with two negative terms.

Euler's formula is recursive because the calculation of p(n) is possible only after the calculation of all the values p(ni ) which, in turn, can be obtained with the same formula.

Taking the previous example

p(10) = p(9) + p(8) - p(5) - p(3)

Then we must calculate p(9), p(8), p(5) e p(3)

By the Euler's formula

To calculate p(10) we must know all the values from p(0) to p(9).

In general, to calculate p(n) we must first calculate all the values from p(0) to p(n-1).

The number of these values coincides with the number of the generalized pentagonal numbers ≤ n.

The following Javascript application allows to obtain the values of p(n) (big numbers may require a lot of computing time).

 

 

fig001.png

As we can see from the picture, p(n) increases rapidly as n increases. For example, p(1000)=24061467864032622473692149727991. This value is given by WolframAlpha®, where the value of p(n) is produced by the function PartitionsP[n] of Mathematica® and where you can change the value of the argument.

For very large values of n many mathematicians have developed increasingly efficient algorithms. For example, Mathematica® applies the method of Hardy- Ramanujan- Rademacher. Recently the mathematician Ken Ono has provided new important contributions.

 


last revision: May 2016