This site is supported by donations to The OEIS Foundation.
Partitions
n |
n |
n |
n |
P (n) |
p (n) |
n |
p (n) |
P (n) |
The set of partitions of 0 is a set containing the empty bag (its sum being the empty sum 0)
-
P (0) = {∅} = {{ }}, p (0) = 1.
The set of partitions of a negative integer is the empty set, since negative integers are not the sum of positive integers
-
P (n) = ∅ = { }, p (n) = 0, n < 0,
where the partition function of negative integers is useful in some recursive formulae for the partition function (e.g. the intermediate partition function formula).
Contents
Definition
An ordinary partition (or line partition) ofn |
-
n0, n1, n2, n3, ⋯
which are nonincreasing (weakly decreasing)
-
ni +1 ≤ ni ,
n |
-
n = ∑ i
n |
Partition function
The partition functionp (n) |
n |
Graphical representations of integer partitions
Ferrers graphs and conjugate partitions
Ferrers graphs (and Ferrers boards) are graphical representations of integer partitions where the parts of the partition are rows of dots (or squares in the case of Ferrers boards). By exchanging rows and columns of the Ferrers graph of a partition, we obtain its conjugate partition. This is equivalent to the transpose of a matrix of dots representing the Ferrers graph. For example, the conjugate partition of {4, 4, 2, 1, 1} is {5, 3, 2, 2}.
|
|
Partition tree
Integer partitions can be generated in a natural way as a binary tree.[1] [2]
Orderings of partitions
- Main article page: Orderings of partitions
Table of partitions in graded reverse lexicographic order
The table adheres to the graded reverse lexicographic ordering of the partitions, also referred to as the “canonical” ordering of the partitions. Partitions ofn |
n − 1 |
Partition | Positive integer representation (
part size
A129129 |
Sum of parts
|
Sum of parts^2 |
Number of parts |
Largest part |
Smallest part | ||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|
{ } | (empty product) 1 | 0 | 0 | 0 | ||||||||
{1} | 2 | 1 | 1 | 1 | 1 | 1 | ||||||
{2} | 3 | 2 | 4 | 1 | 2 | 2 | ||||||
{1,1} | 4 | 2 | 2 | 2 | 1 | 1 | ||||||
{3} | 5 | 3 | 9 | 1 | 3 | 3 | ||||||
{2,1} | 6 | 3 | 5 | 2 | 2 | 1 | ||||||
{1,1,1} | 8 | 3 | 3 | 3 | 1 | 1 | ||||||
{4} | 7 | 4 | 16 | 1 | 4 | 4 | ||||||
{3,1} | 10 | 4 | 10 | 2 | 3 | 1 | ||||||
{2,2} | 9 | 4 | 8 | 2 | 2 | 2 | ||||||
{2,1,1} | 12 | 4 | 6 | 3 | 2 | 1 | ||||||
{1,1,1,1} | 16 | 4 | 4 | 4 | 1 | 1 | ||||||
{5} | 11 | 5 | 25 | 1 | 5 | 5 | ||||||
{4,1} | 14 | 5 | 17 | 2 | 4 | 1 | ||||||
{3,2} | 15 | 5 | 13 | 2 | 3 | 2 | ||||||
{3,1,1} | 20 | 5 | 11 | 3 | 3 | 1 | ||||||
{2,2,1} | 18 | 5 | 9 | 3 | 2 | 1 | ||||||
{2,1,1,1} | 24 | 5 | 7 | 4 | 2 | 1 | ||||||
{1,1,1,1,1} | 32 | 5 | 5 | 5 | 1 | 1 | ||||||
{6} | 13 | 6 | 36 | 1 | 6 | 6 | ||||||
{5,1} | 22 | 6 | 26 | 2 | 5 | 1 | ||||||
{4,2} | 21 | 6 | 20 | 2 | 4 | 2 | ||||||
{4,1,1} | 28 | 6 | 18 | 3 | 4 | 1 | ||||||
{3,3} | 25 | 6 | 18 | 2 | 3 | 3 | ||||||
{3,2,1} | 30 | 6 | 14 | 3 | 3 | 1 | ||||||
{3,1,1,1} | 40 | 6 | 12 | 4 | 3 | 1 | ||||||
{2,2,2} | 27 | 6 | 12 | 3 | 2 | 2 | ||||||
{2,2,1,1} | 36 | 6 | 10 | 4 | 2 | 1 | ||||||
{2,1,1,1,1} | 48 | 6 | 8 | 5 | 2 | 1 | ||||||
{1,1,1,1,1,1} | 64 | 6 | 6 | 6 | 1 | 1 | ||||||
{7} | 17 | 7 | 49 | 1 | 7 | 7 | ||||||
{6,1} | 26 | 7 | 37 | 2 | 6 | 1 | ||||||
{5,2} | 33 | 7 | 29 | 2 | 5 | 2 | ||||||
{5,1,1} | 44 | 7 | 27 | 3 | 5 | 1 | ||||||
{4,3} | 35 | 7 | 25 | 2 | 4 | 3 | ||||||
{4,2,1} | 42 | 7 | 21 | 3 | 4 | 1 | ||||||
{4,1,1,1} | 56 | 7 | 19 | 4 | 4 | 1 | ||||||
{3,3,1} | 50 | 7 | 19 | 3 | 3 | 1 | ||||||
{3,2,2} | 45 | 7 | 17 | 3 | 3 | 2 | ||||||
{3,2,1,1} | 60 | 7 | 15 | 4 | 3 | 1 | ||||||
{3,1,1,1,1} | 80 | 7 | 13 | 5 | 3 | 1 | ||||||
{2,2,2,1} | 54 | 7 | 13 | 4 | 2 | 1 | ||||||
{2,2,1,1,1} | 72 | 7 | 11 | 5 | 2 | 1 | ||||||
{2,1,1,1,1,1} | 96 | 7 | 9 | 6 | 2 | 1 | ||||||
{1,1,1,1,1,1,1} | 128 | 7 | 7 | 7 | 1 | 1 | ||||||
{8} | 19 | 8 | 64 | 1 | 8 | 8 | ||||||
{7,1} | 34 | 8 | 50 | 2 | 7 | 1 | ||||||
{6,2} | 39 | 8 | 40 | 2 | 6 | 2 | ||||||
{6,1,1} | 52 | 8 | 38 | 3 | 6 | 1 | ||||||
{5,3} | 55 | 8 | 34 | 2 | 5 | 3 | ||||||
{5,2,1} | 66 | 8 | 30 | 3 | 5 | 1 | ||||||
{5,1,1,1} | 88 | 8 | 28 | 4 | 5 | 1 | ||||||
{4,4} | 49 | 8 | 32 | 2 | 4 | 4 | ||||||
{4,3,1} | 70 | 8 | 26 | 3 | 4 | 1 | ||||||
{4,2,2} | 63 | 8 | 24 | 3 | 4 | 2 | ||||||
{4,2,1,1} | 84 | 8 | 22 | 4 | 4 | 1 | ||||||
{4,1,1,1,1} | 112 | 8 | 20 | 5 | 4 | 1 | ||||||
{3,3,2} | 75 | 8 | 22 | 3 | 3 | 2 | ||||||
{3,3,1,1} | 100 | 8 | 20 | 4 | 3 | 1 | ||||||
{3,2,2,1} | 90 | 8 | 18 | 4 | 3 | 1 | ||||||
{3,2,1,1,1} | 120 | 8 | 16 | 5 | 3 | 1 | ||||||
{3,1,1,1,1,1} | 160 | 8 | 14 | 6 | 3 | 1 | ||||||
{2,2,2,2} | 81 | 8 | 16 | 4 | 2 | 2 | ||||||
{2,2,2,1,1} | 108 | 8 | 14 | 5 | 2 | 1 | ||||||
{2,2,1,1,1,1} | 144 | 8 | 12 | 6 | 2 | 1 | ||||||
{2,1,1,1,1,1,1} | 192 | 8 | 10 | 7 | 2 | 1 | ||||||
{1,1,1,1,1,1,1,1} | 256 | 8 | 8 | 8 | 1 | 1 |
Positive integer representation of partitions
|
i |
i |
n |
n |
Partitions of
n |
A129129 (concatenated rows)
n |
with odd representation
p (n) |
A000041
_______________
* Rown |
n |
2 n |
** All the partitions of
n |
n − 1 |
n − 1 |
p1 = 2 |
n |
k < n |
Restricted partitions
Sequences
A000041 The number of partitionsp (n) |
n, n ≥ 0 |
- {1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310, 14883, 17977, 21637, 26015, ...}
p (2, n) |
n, n ≥ 0 |
p (n) − p (n − 1), n ≥ 0 |
- {1, 0, 1, 1, 2, 2, 4, 4, 7, 8, 12, 14, 21, 24, 34, 41, 55, 66, 88, 105, 137, 165, 210, 253, 320, 383, 478, 574, 708, 847, 1039, 1238, 1507, 1794, 2167, 2573, 3094, 3660, 4378, 5170, 6153, 7245, 8591, ...}
p (k) |
p (k) = |
k |
- {1, 2, 4, 7, 12, 19, 30, 45, 67, 97, 139, 195, 272, 373, 508, 684, 915, 1212, 1597, 2087, 2714, 3506, 4508, 5763, 7338, 9296, 11732, 14742, 18460, 23025, 28629, 35471, 43820, 53963, 66273, 81156, ...}
n |
n |
- {1, 2, 1, 1, 3, 2, 1, 1, 1, 1, 4, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 6, 5, 1, 4, 2, 4, 1, 1, 3, 3, 3, 2, 1, 3, 1, 1, 1, 2, 2, 2, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 6, 1, 5, 2, 5, 1, 1, 4, 3, 4, 2, 1, 4, 1, 1, 1, 3, 3, 1, 3, 2, ...}
(n) |
- {1, 2, 3, 4, 5, 6, 8, 7, 10, 9, 12, 16, 11, 14, 15, 20, 18, 24, 32, 13, 22, 21, 28, 25, 30, 40, 27, 36, 48, 64, 17, 26, 33, 44, 35, 42, 56, 50, 45, 60, 80, 54, 72, 96, 128, 19, 34, 39, 52, 55, 66, 88, 49, 70, 63, 84, 112, 75, 100, 90, 120, 160, 81, 108, 144, 192, 256, ...}
[P1 + P2 + P3 + ⋯] |
P1 ≥ P2 ≥ P3 ≥ ⋯ |
2 P1 ⋅ 3 P2 ⋅ 5 P3 ⋅ ⋯ |
- {1, 2, 4, 6, 8, 12, 30, 16, 24, 36, 60, 210, 32, 48, 72, 120, 180, 420, 2310, 64, 96, 144, 240, 216, 360, 840, 900, 1260, 4620, 30030, 128, 192, 288, 480, 432, 720, 1680, 1080, 1800, 2520, 9240, 6300, ...}
n |
n |
- {1, 2, 1, 1, 3, 1, 2, 1, 1, 1, 4, 1, 3, 2, 2, 1, 1, 2, 1, 1, 1, 1, 5, 1, 4, 2, 3, 1, 1, 3, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 6, 1, 5, 2, 4, 3, 3, 1, 1, 4, 1, 2, 3, 2, 2, 2, 1, 1, 1, 3, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 7, 1, 6, 2, 5, 3, 4, 1, 1, 5, 1, 2, 4, 1, 3, 3, 2, 2, 3, 1, 1, 1, ...}
A185974 Partitions in Abramowitz-Stegun order [i.e. graded reflected colexicographic ordering] A036036 mapped one-to-one to positive integers.
- {1, 2, 3, 4, 5, 6, 8, 7, 10, 9, 12, 16, 11, 14, 15, 20, 18, 24, 32, 13, 22, 21, 25, 28, 30, 27, 40, 36, 48, 64, 17, 26, 33, 35, 44, 42, 50, 45, 56, 60, 54, 80, 72, 96, 128, 19, 34, 39, 55, 49, 52, 66, 70, 63, 75, 88, 84, 100, 90, 81, 112, 120, 108, 160, 144, 192, 256, 23, 38, 51, 65, 77, 68, 78, ...}
n, n ≥ 2, |
a (n) |
- {1, 2, 3, 4, 5, 7, 6, 9, 8, 12, 10, 19, 13, 14, 11, 30, 16, 45, 15, 21, 20, 67, 17, 22, 31, 25, 23, 97, 24, 139, 18, 32, 46, 33, 27, 195, 68, 47, 26, 272, 35, 373, 34, 37, 98, 508, 28, 49, 36, 69, 50, 684, 40, 48, 38, 99, 140, 915, 39, 1212, 196, 53, 29, 70, 51, 1597, 72, 141, 52, 2087, 42, ...}
|
1 ≤ i < j ≤ n |
i |
j |
n ≥ 1 |
- {0, 0, 1, 2, 4, 6, 10, 15, 23, 36, 47, 70, 87, 132, 283, 434, 471, 772, 825, 1834, 4368, 5545, 5648, 9923, 16464, 19943, 32323, 75912, 76167, 140801, 141140, 238513, 537696, 598295, 2556064, 4674084, ...}
See also
- Unordered partitions
- Partitions and restricted partitions
- Partition function and restricted partition functions
- Partition identities
- Orderings of partitions
- Multidimensional partitions
- Plane partitions (two-dimensional partitions)
- Solid partitions (three-dimensional partitions)
- Prime signature (which may be viewed as a given partition of
, the number of prime factors (with repetition) ofΩ (n)
)n
- Ordered prime signature (which may be viewed as a given composition of
, the number of prime factors (with repetition) ofΩ (n)
)n
Notes
- ↑ Partition-tree of 6, Partition-tree of 7, Partition-tree of 8, Partition-tree of 9, where the seemingly unary branches of the binary tree are actually either a left or right branch with the other branch being an empty branch. (from Peter Luschny, Counting with Partitions, 2009-02-20.)
- ↑ See also User:Peter Luschny/IntegerPartitionTrees.
External links
- M. Abramowitz and I. A. Stegun, eds., Handbook of Mathematical Functions, National Bureau of Standards, Applied Math. Series 55, Tenth Printing, 1972 [alternative scanned copy].
- Jan Hendrik Bruinier and Ken Ono, An Algebraic Formula for the Partition Function.
- Amanda Folsom, Zachary A. Kent, and Ken Ono, p-adic Properties of the Partition Function.
- Jerome Kelleher and Barry O’Sullivan, Generating All Partitions: A Comparison of Two Encodings, 2009.
- Peter Luschny, Counting with Partitions, 2009-02-20.
- Omar E. Pol, 3D image showing the partitions of 1 to 9.
- Steven Finch, Integer Partitions, 2004.