Integer Partitions

MA 367 Spring 2003

Richard Hitt

The Number of Integer Partitions

Mathematica has built-in functions for counting the number of partitions of an integer.  PartitionsP counts the total number of partitions of an integer, while PartitionsQ counts the number of partitions that use distinct summands.

PartitionsP[10]

PartitionsQ[10]

The asymptotic behaviour of these functions can be studied numerically

g1 = ListPlot[Table[{n, Log[PartitionsP[n]]}, {n, 1, 100}]]

g2 = ListPlot[Table[{n, Log[PartitionsQ[n]]}, {n, 1, 100}]]

Show[g1, g2]

Since the natural log of the number of partitions grows like a square root curve, this suggest that the P[n] is of order (e^(n/2)).

Enumerating Partitions

The Combinatorica add-in package has functions that aid in enumerating and other calculations.

<< DiscreteMath`Combinatorica`

Partitions[10]

Partitions[10] // Length

There is also a function for drawing Ferrers diagrams.

FerrersDiagram[RandomPartition[100]]

The Combinatorica add-in also has the ability to enumerate partitions of an integer using summands that don't exceed a given number.

Partitions[10, 3]

We can make a table of these.

Table[Partitions[m, n] // Length, {m, 1, 10}, {n, 1, 10}] // 
      MatrixForm

In order to construct a method for counting the number of partitions of an integer m into exactly n parts, we can use the above function.  Then we can build a table of values for the number of partitions of m using exactly n parts that illustrates the recurrence that we talked about in class.  Of course, this method is very inefficient since it uses the Mathematica functions that actually enumerate the partitions (only counting the total number of such) rather that constructing the numbers using a more efficient recurrence relation.

Clear[a];
a[m_, n_] := 1  /; n == 1
a[m_, n_] := 
      Length[Partitions[m, n]] - Length[Partitions[m, n - 1]] /; 
        n > 1

Table[a[m, n], {m, 1, 25}, {n, 1, 25}] // MatrixForm

Implementing the Recurrence Relation

The above method for generating the table of values is very inefficient since it actually enumerates the partitions and simply counts the number of such.  Since we have a recurrence relation given by

p (m, n) =  (∑_(i = 1)^n) 
          p (m - n, i)

we can directly implement this in Mathematica.

p[m_, n_] := 1 /; n == 1;
p[m_, n_] := 1 /; m == n;
p[m_, n_] := 0 /; n > m;
p[m_, n_] := Sum[p[m - n, i], {i, 1, n}];

We can now define a new function for calculating a table of the partition numbers p(m,n) that runs more efficiently than what we did before.

PartitionTable[a_, 
        b_] := 
TableForm[
Table[
          p[m, n], {m, 1, a}, {n, 1, 
            b}], 
TableSpacing -> {1, 
            1}, 
TableHeadings -> 
          Automatic
]

Now we can use the PartitionTable function to compute tables of a partition numbers much more quickly.

PartitionTable[25, 25]