This site is supported by donations to The OEIS Foundation.

# Orderings of compositions

## Binary representation ordering of the compositions

This ordering is based on binary run-length encoding of finite tuples in nonnegative integers.

${\displaystyle n\,}$ ${\displaystyle n_{2}\,}$ Ordered prime signature Numbers OEIS

number

Prime signature
0 0[1] { } {1}   { }
1 1 {1} {2, 3, 5, 7, 11, 13, 17, 19, ...} A000040 { }
2 10 {1,1} {6, 10, 15, ...} A?????? { }
3 11 {2} { , ...} A?????? { }
4 100 {1,2} { , ...} A?????? { }
5 101 {1,1,1} { , ...} A?????? { }
6 110 {2,1} { , ...} A?????? { }
7 111 {3} { , ...} A?????? { }
8 1000 {1,3} { , ...} A?????? { }
9 1001 {1,2,1} { , ...} A?????? { }
10 1010 {1,1,1,1} { , ...} A?????? { }
11 1011 {1,1,2} { , ...} A?????? { }
12 1100 {2,2} { , ...} A?????? { }
13 1101 {2,1,1} { , ...} A?????? { }
14 1110 {3,1} { , ...} A?????? { }
15 1111 {4} { , ...} A?????? { }
16 10000 {1,4} { , ...} A?????? { }
17 10001 {1,3,1} { , ...} A?????? { }
18 10010 {1,2,1,1} { , ...} A?????? { }
19 10011 {1,2,2} { , ...} A?????? { }
20 10100 {1,1,1,2} { , ...} A?????? { }
21 10101 {1,1,1,1,1} { , ...} A?????? { }
22 10110 {1,1,2,1} { , ...} A?????? { }
23 10111 {1,1,3} { , ...} A?????? { }
24 11000 {2,3} { , ...} A?????? { }
25 11001 {2,2,1} { , ...} A?????? { }
26 11010 {2,1,1,1} { , ...} A?????? { }
27 11011 {2,1,2} { , ...} A?????? { }
28 11100 {3,2} { , ...} A?????? { }
29 11101 {3,1,1} { , ...} A?????? { }
30 11110 {4,1} { , ...} A?????? { }
31 11111 {5} { , ...} A?????? { }
32 100000 {1,5} { , ...} A?????? { }
33 100001 {1,4,1} { , ...} A?????? { }
34 100010 {1,3,1,1} { , ...} A?????? { }
35 100011 {1,3,2} { , ...} A?????? { }
36 100100 {1,2,1,2} { , ...} A?????? { }
37 100101 {1,2,1,1,1} { , ...} A?????? { }
38 100110 {1,2,2,1} { , ...} A?????? { }
39 100111 {1,2,3} { , ...} A?????? { }
40 101000 {1,1,1,3} { , ...} A?????? { }
41 101001 {1,1,1,2,1} { , ...} A?????? { }
42 101010 {1,1,1,1,1,1} { , ...} A?????? { }
43 101011 {1,1,1,1,2} { , ...} A?????? { }
44 101100 {1,1,2,2} { , ...} A?????? { }
45 101101 {1,1,2,1,1} { , ...} A?????? { }
46 101110 {1,1,3,1} { , ...} A?????? { }
47 101111 {1,1,4} { , ...} A?????? { }
48 110000 {2,4} { , ...} A?????? { }
49 110001 {2,3,1} { , ...} A?????? { }
50 110010 {2,2,1,1} { , ...} A?????? { }
51 110011 {2,2,2} { , ...} A?????? { }
52 110100 {2,1,1,2} { , ...} A?????? { }
53 110101 {2,1,1,1,1} { , ...} A?????? { }
54 110110 {2,1,2,1} { , ...} A?????? { }
55 110111 {2,1,3} { , ...} A?????? { }
56 111000 {3,3} { , ...} A?????? { }
57 111001 {3,2,1} { , ...} A?????? { }
58 111010 {3,1,1,1} { , ...} A?????? { }
59 111011 {3,1,2} { , ...} A?????? { }
60 111100 {4,2} { , ...} A?????? { }
61 111101 {4,1,1} { , ...} A?????? { }
62 111110 {5,1} { , ...} A?????? { }
63 111111 {6} { , ...} A?????? { }
64 1000000 {1,6} { , ...} A?????? { }
65 1000001 {1,5,1} { , ...} A?????? { }
66 1000010 {1,4,1,1} { , ...} A?????? { }
67 1000011 {1,4,2} { , ...} A?????? { }
68 1000100 {1,3,1,2} { , ...} A?????? { }
69 1000101 {1,3,1,1,1} { , ...} A?????? { }
70 1000110 {1,3,2,1} { , ...} A?????? { }
71 1000111 {1,3,3} { , ...} A?????? { }
72 1001000 {1,2,1,3} { , ...} A?????? { }
73 1001001 {1,2,1,2,1} { , ...} A?????? { }
74 1001010 {1,2,1,1,1,1} { , ...} A?????? { }
75 1001011 {1,2,1,1,2} { , ...} A?????? { }
76 1001100 {1,2,2,2} { , ...} A?????? { }
77 1001101 {1,2,2,1,1} { , ...} A?????? { }
78 1001110 {1,2,3,1} { , ...} A?????? { }
79 1001111 {1,2,4} { , ...} A?????? { }
80 1010000 {1,1,1,4} { , ...} A?????? { }
81 1010001 {1,1,1,3,1} { , ...} A?????? { }
82 1010010 {1,1,1,2,1,1} { , ...} A?????? { }
83 1010011 {1,1,1,2,2} { , ...} A?????? { }
84 1010100 {1,1,1,1,1,2} { , ...} A?????? { }
85 1010101 {1,1,1,1,1,1,1} { , ...} A?????? { }
86 1010110 {1,1,1,1,2,1} { , ...} A?????? { }
87 1010111 {1,1,1,1,3} { , ...} A?????? { }
88 1011000 {1,1,2,3} { , ...} A?????? { }
89 1011001 {1,1,2,2,1} { , ...} A?????? { }
90 1011010 {1,1,2,1,1,1} { , ...} A?????? { }
91 1011011 {1,1,2,1,2} { , ...} A?????? { }
92 1011100 {1,1,3,2} { , ...} A?????? { }
93 1011101 {1,1,3,1,1} { , ...} A?????? { }
94 1011110 {1,1,4,1} { , ...} A?????? { }
95 1011111 {1,1,5} { , ...} A?????? { }
96 1100000 {2,5} { , ...} A?????? { }
97 1100001 {2,4,1} { , ...} A?????? { }
98 1100010 {2,3,1,1} { , ...} A?????? { }
99 1100011 {2,3,2} { , ...} A?????? { }
100 1100100 {2,2,1,2} { , ...} A?????? { }
101 1100101 {2,2,1,1,1} { , ...} A?????? { }
102 1100110 {2,2,2,1} { , ...} A?????? { }
103 1100111 {2,2,3} { , ...} A?????? { }
104 1101000 {2,1,1,3} { , ...} A?????? { }
105 1101001 {2,1,1,2,1} { , ...} A?????? { }
106 1101010 {2,1,1,1,1,1} { , ...} A?????? { }
107 1101011 {2,1,1,1,2} { , ...} A?????? { }
108 1101100 {2,1,2,2} { , ...} A?????? { }
109 1101101 {2,1,2,1,1} { , ...} A?????? { }
110 1101110 {2,1,3,1} { , ...} A?????? { }
111 1101111 {2,1,4} { , ...} A?????? { }
112 1110000 {3,4} { , ...} A?????? { }
113 1110001 {3,3,1} { , ...} A?????? { }
114 1110010 {3,2,1,1} { , ...} A?????? { }
115 1110011 {3,2,2} { , ...} A?????? { }
116 1110100 {3,1,1,2} { , ...} A?????? { }
117 1110101 {3,1,1,1,1} { , ...} A?????? { }
118 1110110 {3,1,2,1} { , ...} A?????? { }
119 1110111 {3,1,3} { , ...} A?????? { }
120 1111000 {4,3} { , ...} A?????? { }
121 1111001 {4,2,1} { , ...} A?????? { }
122 1111010 {4,1,1,1} { , ...} A?????? { }
123 1111011 {4,1,2} { , ...} A?????? { }
124 1111100 {5,2} { , ...} A?????? { }
125 1111101 {5,1,1} { , ...} A?????? { }
126 1111110 {6,1} { , ...} A?????? { }
127 1111111 {7} { , ...} A?????? { }

## Sequences

Triangle read by rows, in which row n lists the compositions of n in reverse lexicographic order. (Cf. A066099) This is the standard ordering for compositions in this database. (similar to the "Mathematica" ordering of the partitions A080577).

{1, 2, 1, 1, 3, 2, 1, 1, 2, 1, 1, 1, 4, 3, 1, 2, 2, 2, 1, 1, 1, 3, 1, 2, 1, 1, 1, 2, 1, 1, 1, 1, 5, 4, 1, 3, 2, 3, 1, 1, 2, 3, 2, 2, 1, 2, 1, 2, 2, 1, 1, 1, 1, 4, 1, 3, 1, 1, 2, 2, 1, 2, 1, 1, 1, 1, 3, 1, 1, 2, 1, 1, 1, 1, 2, ...}

Table with all compositions sorted first by total, then by length and finally lexicographically. (Cf. A124734) (similar to the "Abramowitz and Stegun" ordering of the partitions, A036036)

{1, 2, 1, 1, 3, 1, 2, 2, 1, 1, 1, 1, 4, 1, 3, 2, 2, 3, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 1, 5, 1, 4, 2, 3, 3, 2, 4, 1, 1, 1, 3, 1, 2, 2, 1, 3, 1, 2, 1, 2, 2, 2, 1, 3, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, ...}

Triangle read by rows: row n gives list of all compositions of n in lexicographical order. (Cf. A108244) (similar to the "Maple" ordering of the partitions, A080576)

{1, 1, 1, 2, 1, 1, 1, 1, 2, 2, 1, 3, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 1, 1, 1, 3, 2, 2, 3, 1, 4, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 1, 1, 1, 1, 3, 1, 2, 2, 2, 1, 2, 1, 3, 1, 2, 2, 1, 3, 1, 1, 1, 4, 2, 3, 3, ...}

Triangle read by rows: n-th row is length of run of leftmost 1's, followed by length of run of 0's, followed by length of run of 1's, etc., in the binary representation of n, A007088. Row n has A005811(n) elements. (Cf. A101211)

{1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 1, 3, 1, 3, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 1, 1, 3, 1, 4, 1, 4, 1, 3, 1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 2, 3, 2, 2, 1, 2, 1, 1, 1, 2, 1, 2, 3, 2, 3, 1, ...}

## Notes

1. We should consider having the empty sum here, the leading zeros not being normally represented (we put the leading zero for zero only to avoid an empty representation for zero, which would not be convenient).