Info on Numerical Partitions

Information on Numerical Partitions

A numerical partition of an integer n is a sequence p₁ > p₂ >· · ·> p_k > 0, such that p₁+p₂+ · · · +p_k = n. Each p_i is called a part. For example, 7+4+4+1+1+1 is a partition of 18 into 6 parts. The number of partitions of n is denoted p(n) and the number of partitions of n into k parts is denoted p(n,k).

p(n,k) = p(n-1, k-1) + p(n-k,k)

The number of numerical partition for n = 1,2,...,15, is p(n) = 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176. This is sequence A000041(M0663) in Neil J. Sloane's database of integer sequences.

Below we show a table of the numbers p(n,k) for 0 < k< n < 9.

k =	1	2	3	4	5	6	7	8
n = 1	1
2	1	1
3	1	1	1
4	1	2	1	1
5	1	2	2	1	1
6	1	3	3	2	1	1
7	1	3	4	3	2	1	1
8	1	4	5	5	3	2	1	1

Representations:

For the partition 7+4+4+1+1+1, the sequence 7 4 4 1 1 1 is called the natural representation. In the multiplicity representation we record how often each integer occurs (e.g., [7,1][4,2][1,3]; meaning 7 occurs once, 4 occurs twice, and 1 occurs 3 times). In the literature, sometimes exponents are used instead (e.g., 7¹ 4² 1³) in the multiplicity representation.

A Ferrers diagram is a pictorial representation of a partition. Each row of the diagram corresponds to one part of the partition; a part of size k is expanded into k dots (or squares). All rows are left-justified. Below is the Ferrers diagram for our example partition.

The algorithm used is from the Combinatorial Generation book.

Partitions with largest part k

The number of partitions of n with largest part k is equal to the number of partitions of n into k parts. To prove this we use the idea of a conjugate partition. This is the partition obtained by flipping the Ferrers diagram about the NW-SE diagonal. The conjugate of our example partition 7+4+4+1+1+1 is 6+3+3+3+1+1+1. See the diagram below for an example of a partition and its conjugate.

7+6+6+1+1

5+3+3+3+3+3+1

Partitions into Odd Parts

Here we consider partitions of n in which every part is odd. The number of such partitions for n=1, 2, ..., 20 is 1, 1, 2, 2, 3, 4, 5, 6, 8, 10, 12, 15, 18, 22, 27, 32, 38, 46, 54, 64. This is sequence A000009 in Neil J. Sloane's database of integer sequences.

Partitions into Distinct Odd Parts

Here we consider partitions of n in which every part is odd and all parts are different. The number of such sequences for n=1, 2, ..., 30 is 1, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 4, 5, 5, 5, 6, 7, 8, 8, 9, 11, 12, 12, 14, 16, 17, 18. This is sequence A000700(M0217) in Neil J. Sloane's database of integer sequences. A partition is self-conjugate if is it equal to its conjugate. There is a well-known correspondence between partitions of n into distinct odd parts and self-conjugate partitions of n. This correspondence is illustrated in the figure below. The idea, in terms of the Ferrers diagram, is to "bend" the distinct odd parts about their middle cell and then stack the bent pieces together.

The Durfee square of a self-conjugate partition is the largest square that may be formed in the upper left corner of the Ferrers diagram. The Durfee square is shown in green if the self-conjugate partitions are output as in the example below. NOT YET IMPLEMENTED!

Ordinary Generating Functions

Numerical partitions give rise to many interesting generating functions and generating function identities. We list below a few of these.

The generating function for unrestricted numerical partitions:

n > 0

p(n) zⁿ

(1-z) (1-z²) (1-z³) (1-z⁴) · · ·

The generating function for partitions whose parts all all odd is the same as that for partitions whose parts are all distinct:

(1+z) (1+z²) (1+z³) (1+z⁴) · · · = 1/(1-z) (1-z³) (1-z⁵) (1-z⁷) · · ·

The generating function for partitions whose parts are all odd and distinct:

(1+z) (1+z³) (1+z⁵) (1+z⁷) · · ·

Interesting Links

From Eric's treasure trove: Partition function P.

Further Tables

A table of the number of parts of size k among all partitions of n.

Programs available: [CAT]

Partitions of n with largest part k. (Pascal program ) (C program )
Partitions of n into odd distinct parts. (Pascal program ) (C program )
Partitions of n in Gray Code order (with largest part k). (Pascal program ) (C program )

Questions?? Email The wizard of COS.

(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 10662 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.