(notes by R. Bigoni)
A finite set S with n elements can be subdivided into k parts p_{i} such that
Each of these possible subdivisions is said a partition of S.
If the elements of S are all distinguishable, the number of its partitions in k parts (or k-partitions) is represented by the symbol , 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:
In fact, let s be any element of S and C_{s} the complementary set of the singleton {s} with respect to S; the number of all possible non-empty subsets Σ_{i} of C_{s} is 2^{n-1}-1; each Σ_{i} identifies a bipartition of S given by Σ_{i} and its complementary with respect to S.
In fact, in this case the number of partitions coincides with the number of the different pairs of elements of S; a partition formed by a pair and by the singletons of the remaining n-2 elements is a partition into n-1 parts.
One gets immediately the following values:
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 because every (k-1)-partition of C united with the singleton {s} forms a k-partition of S.
The partitions of kind Y are , because every k-partition of C united with the singleton {s} forms a k-partition of S.
Assuming
one gets
For n>1, the equation (1,1) allows to derive recursively the Stirling numbers of the second kind.
If n=5:
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.
Writing the Stirling numbers in successive rows with increasing n and k, we get the triangle of Stirling.
We can directly obtain the values of using the Grunert's polynomials. Given a continuous function f(x), we define the operator G such that
If f(x)=e^{x}, we have
Successive applications of G to the results of the previous applications give
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 g^{n}_{k} the coefficients of the polynomial of G^{n}, we have
then
The formation of the coefficients g_{n,k} coincides with the equation (1.1), then
If now we repeatedly apply the operator G to the expansion in Maclaurin series of the natural exponential function we get
By equating the two expressions of G^{n}, we get
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
then
By comparing the sums at both sides, we get
This equation connects the Stirling numbers of the second kind with the binomial coefficients and allows a faster calculation.
Since , from (1.2) we get
By multiplying both the sides of (1.3) by (-1)^{n}
The power (-1)^{2n-j} are identical to powers (-1)^{j}, then
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 B_{n}, named after the mathematician and novelist E. T. Bell.
The Bell numbers can be recursively obtained with the following procedure
that is
in any new row:
In this way we can build the Bell triangle.
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®.
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 B_{4} = 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,i} ≤ n
such that
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 .
The number 2 admits two partitions:
The number 3 admits three partitions:
The number 4 admits five partitions:
The number 5 admits seven partitions::
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
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(n_{i} ) of all the numbers that are obtained by subtracting from n the generalized pentagonal numbers ω_{i}≤n. We assume p(0)=1.
The set Ω of generalized pentagonal numbers ω_{i} is obtained from the union of sequences of natural numbers defined as follows
If, for example, n=10, the numbers n_{i} obtained by subtracting 10 from the generalized pentagonal numbers ω_{i} ≤10 are:
The Euler's recursive formula states that, given the maximum index i_{M} for the numbers n_{i}
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(n_{i} ) 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).
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