Orderings of partitions

This article needs more work.

Please help by expanding it!

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; 
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.

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.)

Orderings comparison table for partitions of 6

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

• Orderings
• Integer partition trees