Partition HOWTO (English version)

This HOWTO explains how to use integer partitions in NZMATH. Note that a part of features explained here is not provided in the current released versions, but will be released in the next version. If you are interested in the features, please clone the mercurial repository available on sourceforge.net:

% hg clone http://nzmath.hg.sourceforge.net:8000/hgroot/nzmath/nzmath

1. Partition

A partition of a natural number n means a sum of natural numbers whose evaluated value is n. For example, 2+2+1 is a partition of 5. As sum does not change its value even if the order of terms are changed, we do not care about the order of summands. That is, we do not distinguish 2+2+1, 2+1+2 and 1+2+2. The partitions often appear when we consider a combinatorial structure. Thus NZMATH has the related functions in the combinatorial module. We assume to have imported the module as from nzmath.combinatorial import * in the following examples.

The first thing we have to know is how to obtain the partitions. We use the partition_generator.

>>> for partition in partition_generator(5):
...     print partition
...
(5,)
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

These are the whole partitions of 5. Instead of an expression of addition, the generator yields tuples of summands.

There has been seven partitions of 5, you may wonder how the number of partitions increase along with increasing n from 5. In principle, you can get the numbers by len(list(partition_generator(n))), but it is inefficient; we have another function to calculate the number of partitions only:

>>> partition_number(6)
11
>>>

We shall not use the function in this HOWTO anymore. The number of partitions increases almost exponentially.

2. Partition with limited maximum

Let's think about the case when a limit of maximum of summands is set. That is for example, we would like to obtain the partitions of 5 whose summands are less than or equal to three. The simplest strategy discarding unnecessary partitions looks like this:

>>> for partition in partition_generator(5):
...     if all(d <= 3 for d in partition):
...         print partition
...
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

This kind of "filtering" is not a wrong approach. It can be the best way in general if there is no other means. However, this section is written to say: "partition_generator can take the second argument."

>>> for partition in partition_generator(5, 3):
...     print partition
...
(3, 2)
(3, 1, 1)
(2, 2, 1)
(2, 1, 1, 1)
(1, 1, 1, 1, 1)
>>>

3. Partition with limited number of summands

Next situation is that the number of summands is limited. In the partitions of 5, we only need the number of summands is less than or equal to 3, say. Again, we start with a general method of filtering.

>>> for partition in partition_generator(5):
...     if len(partition) <= 3:
...         print partition
...
(5, )
(4, 1)
(3, 2)
(3, 1, 1)
(2, 2, 1)
>>>

By the way, the number of partitions of 5 into parts less than or equal to 3 is five and into less than or equal to 3 parts is also five. This is not an accident, i.e., there is a one-to-one correspondence between them called "conjugate". The conjugation is easy to understand through diagrams (called the Young diagram or the Ferrers diagram). The left diagram is (4, 1), and right (2, 1, 1, 1).

. . . .    . .
.          .
           .
           .

Counting points in rows from top to bottom gives (4, 1) to the left diagram and (2, 1, 1, 1) right. The conjugation is an operation of these diagrams; fix the left top corner and turn over the plane. The partition (4, 1) can be seen as the conjugate partition of (2, 1, 1, 1).

NZMATH has the function partition_conjugate.

>>> for partition in partition_generator(5, 3):
...     print partition_conjugate(partition)
...
(2, 2, 1)
(3, 1, 1)
(3, 2)
(4, 1)
(5,)
>>>

The order is different (accidentally in the reverse order), but the partitions are the same.

4. Partition with maximum exactly equal to k

The previous sections merely introduce the pre-defined functions. Now, we start to construct some kinds of partitions as needed. We have already seen the second argument for partition_generator makes it possible to partition a number into parts "at most k". Then, how to construct a partition with the maximum part exactly equal to k? Of course, filtering strategy still works, but you can construct such partitions without any to-be-filtered partitions. Notice that the "part exactly equal to k" is common among the necessary partitions. Then, by concatenating it with partitions of n-k into parts at most k, the partitions of n with the maximum exactly equal to k can be obtained.

# n=6, k=3
>>> for partition in partition_generator(6-3, 3):
...     print (3,)+partition
...
(3, 3)
(3, 2, 1)
(3, 1, 1, 1)
>>>

Problem: How to construct the partitions of n into exactly k parts? (hint: use conjugate.)

5. Partition with limited minimum

We have already covered the way to restrict the maximum of summands or of the number of summands. Next problem is how to restrict the minimum of them. For example, how to obtain the partition of 7 whose summands are at least 2. The conjugation is useful for this situation, again. A partition into parts at least 2 is conjugate to a partition with at least 2 biggest parts. Thus, this is an extension of the previous section.

>>> n=7; k=2
>>> for m in range(1, n//k + 1):
...     for partition in partition_generator(n - m*k, m):
...         print (m,)*k + partition:
... 
(1, 1, 1, 1, 1, 1, 1)
(2, 2, 2, 1)
(2, 2, 1, 1, 1)
(3, 3, 1)
>>>

The partition we need are the conjugates of them.

>>> n=7; k=2
>>> for m in range(1, n//k + 1):
...     for partition in partition_generator(n - m*k, m):
...         print partition_conjugate((m,)*k + partition):
... 
(7,)
(4, 3)
(5, 2)
(3, 2, 2)
>>>

6. Partition into odd parts

Next target is, much different to the previous sections, partition into odd parts. The partitions of 9 into odd parts, for example, are:

(9,)
(7, 1, 1)
(5, 3, 1)
(5, 1, 1, 1, 1)
(3, 3, 3)
(3, 3, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1)

The number of partitions of 9 is thirty, but the number of those into odd parts is only eight. Considering the difference, filtering should be avoided. By the following correspondence:

9 = 2*5 - 1
7 = 2*4 - 1
...
1 = 2*1 - 1

odd numbers and natural numbers are mapped one-to-one. Then the partitions are mapped:

(9,)                        ⟷ (5,)
(7, 1, 1)                   ⟷ (4, 1, 1)
(5, 3, 1)                   ⟷ (3, 2, 1)
(5, 1, 1, 1, 1)             ⟷ (3, 1, 1, 1, 1)
(3, 3, 3)                   ⟷ (2, 2, 2)
(3, 3, 1, 1, 1)             ⟷ (2, 2, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)       ⟷ (2, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1) ⟷ (1, 1, 1, 1, 1, 1, 1, 1, 1)

You can see that the right hand sides consist of the partition of 5 into exactly 1 part, the partitions of 6 into exactly 3 parts, ... and the partition of 9 into exactly 9 parts. The partitions of n into exactly k parts is known by the problem of section 4, thus we can use it.

>>> n = 9
>>> for m in range(n//2 + 1, n + 1):
...     for partition in partition_generator(n - m, 2*m - n):
...         print tuple(2*x - 1 for x in partition_conjugate((2*m - n,) + partition))
... 
(9,)
(3, 3, 3)
(5, 3, 1)
(7, 1, 1)
(3, 3, 1, 1, 1)
(5, 1, 1, 1, 1)
(3, 1, 1, 1, 1, 1, 1)
(1, 1, 1, 1, 1, 1, 1, 1, 1)
>>> 

Problem: A partition into odd parts is mapped one-to-one to a partition into different parts by applying the rule "fuse two same parts." By this fact, obtain the partitions of n into different parts.

7. Conclusion

We have explained the way to construct the partitions, from plain partitions to partitions with some limitations. The last one or two seems rather easy if we write specialized generator, but anyway you can grasp how to construct the partitions through a certain one-to-one correspondence. We will continue the exploration in HOWTO II, where we will explain such specialized generators.

References:
G.E.Andrews and K.Eriksson. Integer Partitions. Cambridge University Press.