Integer partition
In mathematics, a partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums which only differ in the order of their summands are considered to be the same partition. A summand in a partition is also called
a part.
Examples
The partitions of 4 are listed below:
- 4
- 3 + 1
- 2 + 2
- 2 + 1 + 1
- 1 + 1 + 1 + 1
The partitions of 8 are listed below:
- 8
- 7 + 1
- 6 + 2
- 6 + 1 + 1
- 5 + 3
- 5 + 2 + 1
- 5 + 1 + 1 + 1
- 4 + 4
- 4 + 3 + 1
- 4 + 2 + 2
- 4 + 2 + 1 + 1
- 4 + 1 + 1 + 1 + 1
- 3 + 3 + 2
- 3 + 3 + 1 + 1
- 3 + 2 + 2 + 1
- 3 + 2 + 1 + 1 + 1
- 3 + 1 + 1 + 1 + 1 + 1
- 2 + 2 + 2 + 2
- 2 + 2 + 2 + 1 + 1
- 2 + 2 + 1 + 1 + 1 + 1
- 2 + 1 + 1 + 1 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Among the 22 partitions for the number 8, 6 of them contain
only odd parts:
- 7 + 1
- 5 + 3
- 5 + 1 + 1 + 1
- 3 + 3 + 1 + 1
- 3 + 1 + 1 + 1 + 1 + 1
- 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
Curiously, if we count the partitions of 8
with distinct parts, we also obtain the number 6:
- 8
- 7 + 1
- 6 + 2
- 5 + 3
- 5 + 2 + 1
- 4 + 3 + 1
Is this only coincidence, or is it true that, for all positive numbers,
the number of partitions with odd parts always equals the number
of partitions with distinct parts? This and other results
can be obtained by the aid of a visual tool, Ferrers' graph.
Ferrers' graph
The partition 6 + 4 + 3 + 1 of the positive number 14 can be represented
by the following graph:
o o o o
o o o
o o o
o o
o
o
6+4+3+1
The 14 circles are lined up in 4 columns, each having the size of a part
of the partition. The graphs for the 5 partitions of the number 4 are
listed below:
o o o o o o o o o o o o
o o o o o
o o
o
4 3+1 2+2 2+1+1 1+1+1+1
If we now flip the graph of the partition 6 + 4 + 3 + 1 along the
NW-SE axis, we obtain another partition of 14:
o o o o o o o o o o
o o o o o o o
o o o --> o o o
o o o
o
o
6+4+3+1 4+3+3+2+1+1
By turning the rows into columns, we obtain the partition 4 + 3 + 3 + 2 +
1 + 1 of the number 14. Such partitions are said to be
conjugate of one another. In the case of the number 4, partitions
4 and 1 + 1 + 1 + 1 are conjugate pairs, and partitions 3 + 1 and 2 + 1 + 1
are conjugate of each other. Of particular interest is the partition
2 + 2, which has itself as conjugate. Such a paritition is said to be
self-conjugate.
Claim: The number of self-conjugate partitions is the same as the
number of partitions with distinct odd parts.
Proof (sketch): The crucial observation is that every odd part can
be "folded" in the middle to form a self conjugate graph:
o
o
o --> o o o
o o
o o
One can then obtain a bijection between the set of partitions with distinct
odd parts and the set of self-conjugate partitions, as illustrated by
the following example:
o * x o o o o o
o * x o * * * *
o * x <--> o * x x
o * o * x
o * o *
o *
o *
o
o
9+7+3 5+5+4+3+2
distinct odd self-conjugate
Similar techniques can be employed to establish, for example, the following
equalities:
- The number of partitions of n into no more than k parts is the same as the number of partitions of n into parts no larger than k.
- The number of partitions of n into no more than k parts is the same as the number of partitions of n+k into exactly k parts.
Number of partitions
The number of partitions of a positive integer n is given by the partition function p(n). The number of partitions of n into
exactly k parts is denoted by pk(n).
Ferrers graph techniques also allow us to prove results like the following:
- There are p(n) - p(n-1) partitions of n in which each part is at least 2.
- p(1) + p(2) + ... + p(n) < p(2n)
See also
Bibliographical notes
An elementary introduction to the topic of integer partition, including
discussion of Ferrers' graph, can be found in the following reference:
- Miklós Bóna, A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, World Scientific Publishing, 2002. ISBN 9810249004.
External links
Referenced By
List of mathematical proofs | List of mathematical topics (G-I) | List of mathematical topics (G-Z) | List of number theory topics | List of proofs | Partition | Partition (computers) | Partition (mathematics) | Pentagonal number theorem
|
