Editing Lexicographic order (section)

==Colexicographic order==
[[File:Orderings; permutations 5-cycle.svg|thumb|340px|Orderings of the 24 permutations of {1,...,5} that are [[Cycles and fixed points|5-cycles]] (in blue). The [[Inversion (discrete mathematics)|inversion vectors]] (in red) of permutations in ''colex'' order are in ''revcolex'' order, and vice versa.]]

The '''colexicographic''' or '''colex order''' is a variant of the lexicographical order that is obtained by reading finite sequences from the right to the left instead of reading them from the left to the right.  More precisely, whereas the lexicographical order between two sequences is defined by

:{{math|''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub> <<sup>lex</sup> ''b''<sub>1</sub>''b''<sub>2</sub> ... ''b''<sub>''k''</sub>}} if {{math|''a<sub>i</sub>'' < ''b<sub>i</sub>''}} for the first {{math|''i''}} where {{math|''a<sub>i</sub>''}} and {{math|''b<sub>i</sub>''}} differ,
the colexicographical order is defined by

:{{math|''a''<sub>1</sub>''a''<sub>2</sub>...''a''<sub>''k''</sub> <<sup>colex</sup> ''b''<sub>1</sub>''b''<sub>2</sub>...''b''<sub>''k''</sub>}} if {{math|''a<sub>i</sub>'' < ''b<sub>i</sub>''}} for the last {{math|''i''}} where {{math|''a<sub>i</sub>''}} and {{math|''b<sub>i</sub>''}} differ

In general, the difference between the colexicographical order and the lexicographical order is not very significant. However, when considering increasing sequences, typically for coding subsets, the two orders differ significantly.

For example, for ordering the increasing sequences (or the sets) of two natural integers, the lexicographical order begins by

:{{math|12 < 13 < 14 < 15 < ... < 23 < 24 < 25 < ... < 34 < 35 < ... < 45 < ...}}, 

and the colexicographic order begins by

:{{math|12 < 13 < 23 < 14 < 24 < 34 < 15 < 25 < 35 < 45 < ...}}.

The main property of the colexicographical order for increasing sequences of a given length is that every [[initial segment]] is finite. In other words, the colexicographical order for increasing sequences of a given length induces an [[order isomorphism]] with the natural numbers, and allows enumerating these sequences. This is frequently used in [[combinatorics]], for example in the proof of the [[Kruskal–Katona theorem]].