Information on Numerical Partitions
A numerical partition of an integer n
is a sequence p_{1} >
p_{2} >· · ·>
p_{k} > 0,
such that p_{1}+p_{2}+
· · ·
+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(n1,
k1)
+ p(nk,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^{1} 4^{2} 1^{3}) 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 leftjustified.
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 NWSE 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.
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 selfconjugate if is it equal to its conjugate.
There is a wellknown correspondence between partitions of n
into distinct odd parts and selfconjugate 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 selfconjugate 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 selfconjugate 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:

p(n) z^{n}

=

1

 (1z) (1z^{2}) (1z^{3})
(1z^{4}) · · ·


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^{2}) (1+z^{3})
(1+z^{4})
· · ·
=
1/(1z) (1z^{3}) (1z^{5}) (1z^{7})
· · ·
The generating function for partitions whose parts are all odd and
distinct:
(1+z) (1+z^{3}) (1+z^{5})
(1+z^{7})
· · ·
Interesting Links
Further Tables

A table of the number of parts
of size k among all partitions of n.
Programs available:
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, 10May2006 10:32:14 PDT.
[Error Opening Counter File  Click for more info]
©Frank Ruskey, 19952003.