This site is supported by donations to The OEIS Foundation.
Orderings of partitions
Contents
- 1 Graded lexicographical ordering of the partitions
- 2 “Canonical” ordering of the partitions
- 3 “Abramowitz and Stegun” ordering of the partitions
- 4 “Maple” ordering of the partitions
- 5 “Mathematica” ordering of the partitions
- 6 Pari/GP partitions
- 7 Other orderings for the partitions
- 8 Summary
- 9 A comparison
- 10 See also
- 11 Notes
Graded lexicographical ordering of the partitions
The partitions for n = 0 to 6 in graded lexicographical ordering are
{{}} {{1}} {{1, 1}, {2}} {{1, 1, 1}, {2, 1}, {3}} {{1, 1, 1, 1}, {2, 1, 1}, {2, 2}, {3, 1}, {4}} {{1, 1, 1, 1, 1}, {2, 1, 1, 1}, {2, 2, 1}, {3, 1, 1}, {3, 2}, {4, 1}, {5}} {{1, 1, 1, 1, 1, 1}, {2, 1, 1, 1, 1}, {2, 2, 1, 1}, {2, 2, 2}, {3, 1, 1, 1}, {3, 2, 1}, {3, 3}, {4, 1, 1}, {4, 2}, {5, 1}, {6}} ...
Here the partitions are ordered by increasing sum n, and then in lexicographically increasing order, for partitions written with terms in decreasing size.
“Canonical” ordering of the partitions
The “canonical” ordering of the partitions refers to the graded reverse lexicographic ordering of the partitions.
Partitions are ordered first by sum. Then all partitions of n are viewed as exponent tuples on n variables and their corresponding monomials are ordered reverse lexicographically. This gives a “canonical” ordering of the partitions.
The partitions of each integer are in reverse order of the conjugates of the partitions in “Abramowitz and Stegun” order (A036036). They are in the reverse of the order of the partitions in “Maple” order (A080576). — Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Oct 18 2006
The partitions for n = 0 to 6 in “canonical” ordering are
{{}} {{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}} ...
Triangle in which row n lists all partitions of n in the order produced by Mathematica (“canonical” ordering of the partitions) (A080577).
- {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, ...}
The canonical partition sequence (A080577) encoded by prime factorization. The partition [P1 + P2 + P3 + ...] with P1 >= P2 >= P3 >= ... is encoded as 2^P1 * 3^P2 * 5^P3 *... (A063008) gives
- {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, 13860, ...}
“Abramowitz and Stegun” ordering of the partitions
“Abramowitz and Stegun” ordering of the partitions (parts in increasing order)
This “Abramowitz and Stegun” ordering of the partitions, referenced in numerous other sequences is the graded reflected colexicographic ordering of the partitions.
The partitions are in reverse order of the conjugates of the partitions in “Mathematica” order (A080577). Each partition is the conjugate of the corresponding partition in “Maple” order (A080576). — Franklin T. Adams-Watters, Oct 18 2006
Partitions are thus ordered firstly by increasing sum of parts n, then by increasing number of parts, then by increasing lexicographical order of partitions with increasing parts, e.g., [1, 3, 5] comes before [1, 4, 4] which comes before [2, 2, 5]. (The largest part may decrease or increase from one partition to the next, although it is non-increasing for partitions of equal length up to n = 8: the preceding example is the first counter-example.)
The partitions for n = 0 to 6 in “Abramowitz and Stegun” (parts in increasing order) ordering are[1]
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; ...
Triangle read by rows: row n lists partitions of n (A036036).
- {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, ...}
Alternative (non-reflected) “Abramowitz and Stegun” ordering of the partitions (parts in decreasing order)
This is the alternative (non-reflected) “Abramowitz and Stegun” ordering of the partitions, referenced in numerous (?) other sequences. The alternative (non-reflected) “Abramowitz and Stegun” ordering of the partitions (parts in decreasing order) is the graded colexicographic ordering of the partitions.
The partitions are in reverse order of the conjugates of the partitions in “Mathematica” order (A080577). Each partition is the conjugate of the corresponding partition in “Maple” order (A080576).
Partitions are thus ordered firstly by increasing n (sum of parts), then secondarily by increasing number of parts.
The partitions for n = 0 to 6 in “Abramowitz and Stegun” (parts in decreasing order) ordering are
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; 3,3; 4,1,1; 3,2,1; 2,2,2; 3,1,1,1; 2,2,1,1; 2,1,1,1,1; 1,1,1,1,1,1; ...
Triangle read by rows in which row n lists all the parts (in decreasing order) of all the partitions of n (A036037).
- {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, 3, 3, 4, 1, 1, 3, 2, 1, 2, 2, 2, 3, 1, 1, 1, 2, 2, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 7, 6, 1, 5, 2, 4, ...}
“Maple” ordering of the partitions
This is the “Maple” ordering of the partitions, referenced in numerous other sequences. The “Maple” ordering of the partitions is the graded reflected lexicographic ordering of the partitions.
Each partition here is the conjugate of the corresponding partition in “Abramowitz and Stegun” order (A036036). The partitions are in the reverse of the order of the partitions in “Mathematica” order (A080577). — Franklin T. Adams-Watters (FrankTAW(AT)Netscape.net), Oct 18 2006
The partitions for n = 0 to 6 in “Maple” ordering are
[[]] [[1]] [[1, 1], [2]] [[1, 1, 1], [1, 2], [3]] [[1, 1, 1, 1], [1, 1, 2], [2, 2], [1, 3], [4]] [[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 2, 2], [1, 1, 3], [2, 3], [1, 4], [5]] [[1, 1, 1, 1, 1, 1], [1, 1, 1, 1, 2], [1, 1, 2, 2], [2, 2, 2], [1, 1, 1, 3], [1, 2, 3], [3, 3], [1, 1, 4], [2, 4], [1, 5], [6]] ...
Triangle in which row n lists all partitions of n, in order produced by Maple (A080576).
- {1, 1, 1, 2, 1, 1, 1, 1, 2, 3, 1, 1, 1, 1, 1, 1, 2, 2, 2, 1, 3, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 2, 1, 1, 3, 2, 3, 1, 4, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 2, 2, 2, 1, 1, 1, 3, 1, 2, 3, 3, 3, 1, 1, 4, 2, 4, 1, 5, 6, 1, 1, 1, 1, 1, 1, ...}
“Mathematica” ordering of the partitions
This is the “Mathematica” ordering of the partitions, referenced in numerous other sequences. The “Mathematica” ordering of the partitions is the graded reverse lexicographic ordering of the partitions, also referred to as the “canonical” ordering of the partitions.
Pari/GP partitions
This file by Richard Mathar produces the partitions: Partition_Pari.txt
Other orderings for the partitions
See coding integer partitions with binary run-length encoding and Marc LeBrun’s encoding for partitions based on prime factorization[2].
Summary
Ref Lex reflected lexicographic A080576 “Maple” ordering Rev Lex reverse lexicographic A080577 “Mathematica” ordering Ref CoLex reflected colexicographic A036036 “Abramowitz and Stegun” ordering
A comparison
Since the partitions are sets of positive integers, the sets have different cardinality. For the sake of comparing the orderings of partitions, it is convenient to have sets with same cardinality by adding parts of value 0.
Lex and Colex, Ref Lex and Ref Colex, Rev Lex and Rev Colex, Rev Ref Lex and Rev Ref Colex constitute four pairs of conjugate partitions (transpose partitions) (Cf. Ferrers diagram.)
Lex | Ref Lex |
Rev Lex |
Rev Ref Lex |
Colex | Ref Colex |
Rev Colex |
Rev Ref Colex |
1, 1, 1, 1, 1, 1 | 1, 1, 1, 1, 1, 1 | 6, 0, 0, 0, 0, 0 | 0, 0, 0, 0, 0, 6 | 6, 0, 0, 0, 0, 0 | 0, 0, 0, 0, 0, 6 | 1, 1, 1, 1, 1, 1 | 1, 1, 1, 1, 1, 1 |
2, 1, 1, 1, 1, 0 | 0, 1, 1, 1, 1, 2 | 5, 1, 0, 0, 0, 0 | 0, 0, 0, 0, 1, 5 | 5, 1, 0, 0, 0, 0 | 0, 0, 0, 0, 1, 5 | 2, 1, 1, 1, 1, 0 | 0, 1, 1, 1, 1, 2 |
2, 2, 1, 1, 0, 0 | 0, 0, 1, 1, 2, 2 | 4, 2, 0, 0, 0, 0 | 0, 0, 0, 0, 2, 4 | 4, 2, 0, 0, 0, 0 | 0, 0, 0, 0, 2, 4 | 2, 2, 1, 1, 0, 0 | 0, 0, 1, 1, 2, 2 |
2, 2, 2, 0, 0, 0 | 0, 0, 0, 2, 2, 2 | 4, 1, 1, 0, 0, 0 | 0, 0, 0, 1, 1, 4 | 3, 3, 0, 0, 0, 0 | 0, 0, 0, 0, 3, 3 | 3, 1, 1, 1, 0, 0 | 0, 0, 1, 1, 1, 3 |
3, 1, 1, 1, 0, 0 | 0, 0, 1, 1, 1, 3 | 3, 3, 0, 0, 0, 0 | 0, 0, 0, 0, 3, 3 | 4, 1, 1, 0, 0, 0 | 0, 0, 0, 1, 1, 4 | 2, 2, 2, 0, 0, 0 | 0, 0, 0, 2, 2, 2 |
3, 2, 1, 0, 0, 0 | 0, 0, 0, 1, 2, 3 | 3, 2, 1, 0, 0, 0 | 0, 0, 0, 1, 2, 3 | 3, 2, 1, 0, 0, 0 | 0, 0, 0, 1, 2, 3 | 3, 2, 1, 0, 0, 0 | 0, 0, 0, 1, 2, 3 |
3, 3, 0, 0, 0, 0 | 0, 0, 0, 0, 3, 3 | 3, 1, 1, 1, 0, 0 | 0, 0, 1, 1, 1, 3 | 2, 2, 2, 0, 0, 0 | 0, 0, 0, 2, 2, 2 | 4, 1, 1, 0, 0, 0 | 0, 0, 0, 1, 1, 4 |
4, 1, 1, 0, 0, 0 | 0, 0, 0, 1, 1, 4 | 2, 2, 2, 0, 0, 0 | 0, 0, 0, 2, 2, 2 | 3, 1, 1, 1, 0, 0 | 0, 0, 1, 1, 1, 3 | 3, 3, 0, 0, 0, 0 | 0, 0, 0, 0, 3, 3 |
4, 2, 0, 0, 0, 0 | 0, 0, 0, 0, 2, 4 | 2, 2, 1, 1, 0, 0 | 0, 0, 1, 1, 2, 2 | 2, 2, 1, 1, 0, 0 | 0, 0, 1, 1, 2, 2 | 4, 2, 0, 0, 0, 0 | 0, 0, 0, 0, 2, 4 |
5, 1, 0, 0, 0, 0 | 0, 0, 0, 0, 1, 5 | 2, 1, 1, 1, 1, 0 | 0, 1, 1, 1, 1, 2 | 2, 1, 1, 1, 1, 0 | 0, 1, 1, 1, 1, 2 | 5, 1, 0, 0, 0, 0 | 0, 0, 0, 0, 1, 5 |
6, 0, 0, 0, 0, 0 | 0, 0, 0, 0, 0, 6 | 1, 1, 1, 1, 1, 1 | 1, 1, 1, 1, 1, 1 | 1, 1, 1, 1, 1, 1 | 1, 1, 1, 1, 1, 1 | 6, 0, 0, 0, 0, 0 | 0, 0, 0, 0, 0, 6 |
See also
Notes
- ↑ Abramowitz and Stegun, Handbook, p. 831, column labeled π.
- ↑ Marc LeBrun’s original “crazy order” mapping for partitions.