This site is supported by donations to The OEIS Foundation.

# Orderings

An ordering (or order) is a method for sorting elements.

## Contents

- 1 Types of orderings
- 2 Orderings of partitions
- 3 Orderings of compositions
- 4 Orderings of combinatorial interpretations of Catalan numbers
- 5 Orderings of prime signatures
- 6 Orderings of ordered prime signatures
- 7 Orderings of rational integers
- 8 Orderings of rational numbers
- 9 Orderings of algebraic numbers
- 10 See also
- 11 External links

## Types of orderings

### 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* |
RevRef Lex* |
CoLex* | Ref CoLex* |
Rev CoLex* |
RevRef 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 |

### Lexicographic order

In mathematics, the lexicographic, lexicographical order or lex order, (also known as dictionary order, alphabetical order or lexicographic(al) product), is a natural order structure of the Cartesian product of two or more ordered sets.

Given two partially ordered sets and , the lexicographical order on the Cartesian product is defined as

The result is a partial order. If and are totally ordered sets, then the result is a total order as well.

One can define the lexicographic order on the Cartesian product of ordered sets.

Suppose

is an -tuple of sets, with respective total orderings

The lex ordering is then

The following is a lex ordering on subsets of size 3 from the set :

More generally, one can define the lexicographic order on the Cartesian product of ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

When applied to numbers, lexicographic order is increasing numerical order, i.e. increasing numerical order (numbers read left to right). For example, the permutations of {1,2,3} in lexicographic order are 123, 132, 213, 231, 312, and 321.

When applied to subsets, two subsets are ordered by their smallest elements. For example, the subsets of {1,2,3} in lexicographic order are {}, {1}, {1,2}, {1,2,3}, {1,3}, {2}, {2,3}, {3}.

### Reverse lexicographic order

The reverse lexicographic order is derived from the lexicographic order by inverting the external order of elements.

The following is a **reverse lex ordering** on subsets of size 3 from the set :

### Reflected lexicographic order

The reflected lexicographic order is derived from the lexicographic order by inverting the internal order of elements.

The following is a **reflected lex ordering** on subsets of size 3 from the set :

### Reverse reflected lexicographic order

The reverse reflected lexicographic order is derived from the lexicographic order by inverting both the internal order and the external order of elements.

The following is a **reverse reflected lex ordering** on subsets of size 3 from the set :

### Colexicographic order

In mathematics, the colexicographic, colexicographical order or colex order, (also known as colexicographic(al) product), is a natural order structure of the Cartesian product of two or more ordered sets. It is similar in structure to the lexicographical order. Colexicographical ordering is used in the Kruskal-Katona theorem.

Given two partially ordered sets and , the colexicographical order on the Cartesian product is defined as

The result is a partial order. If and are totally ordered, then the result is a total order also.

One can define the colexicographic order on the Cartesian product of ordered sets.

Suppose

is an -tuple of sets, with respective total orderings

The colex ordering is then

The following is a colex ordering on subsets of size 3 from the set :

More generally, one can define the colexicographic order on the Cartesian product of ordered sets, on the Cartesian product of a countably infinite family of ordered sets, and on the union of such sets.

When applied to numbers, colexicographic order is increasing numerical order (numbers read right to left). For example, the permutations of {1,2,3} in colexicographic order are 321, 231, 312, 132, 213, and 123.

When applied to subsets, two subsets are ordered by their greatest elements. For example, the subsets of {1,2,3} in colexicographic order are {}, {1}, {2}, {1,2}, {3}, {1,3}, {2,3}, {1,2,3}.

### Reverse colexicographic order

The reverse colexicographic order is derived from the colexicographic order by inverting the external order of elements.

The following is a **reverse colex ordering** on subsets of size 3 from the set :

### Reflected colexicographic order

The reflected colexicographic order is derived from the colexicographic order by inverting the internal order of elements.

The following is a **reflected colex ordering** on subsets of size 3 from the set :

### Reverse reflected colexicographic order

The reverse reflected colexicographic order is derived from the colexicographic order by inverting both the internal order and the external order of elements.

The following is a **reverse reflected colex ordering** on subsets of size 3 from the set :

## Orderings of partitions

### Graded orderings of partitions

The partitions of nonnegative integers may be sorted with a graded ordering, where we first order by increasing (sum of the parts,) which corresponds to the grade of the ordering, then by one of the eight above mentioned orderings.

## Orderings of compositions

### Graded orderings of compositions

The compositions of nonnegative integers may be sorted with a graded ordering, where we first order by increasing (sum of the ordered parts,) which corresponds to the grade of the ordering, then by one of the eight above mentioned orderings.

Cf. Orderings of compositions.

## Orderings of combinatorial interpretations of Catalan numbers

*Main article page: Orderings of combinatorial interpretations of Catalan numbers*

There are various ways to bijectively map the combinatorial interpretations of Catalan numbers (e.g. binary trees, general trees, Dyck paths, noncrossing set partitions, etc.) to natural numbers, and thus each such a mapping gives a particular total order for those Catalan families.

## Orderings of prime signatures

### Graded orderings of prime signatures

The prime signatures of positive integers are usually sorted in graded reflected colexicographic order, i.e. graded by increasing , then by reflected colexicographic order of exponents (which nicely sorts by increasing ). With this convention, the prime signature internal order has the exponents in increasing order.

The prime signatures of positive integers may also be sorted in graded colexicographic order, i.e. graded by increasing , then by colexicographic order of exponents (which nicely sorts by increasing ).With this convention, the prime signature internal order has the exponents in decreasing order, which nicely corresponds to the order of exponents of the smallest numbers of prime signatures, where the prime factors are commonly listed from smallest to largest.

Cf. Prime signatures in graded colexicographic order.

### Prime signatures in the order of increasing smallest numbers of prime signatures

Cf. Prime signatures in the order of increasing smallest numbers of prime signatures.

## Orderings of ordered prime signatures

### Graded orderings of ordered prime signatures

### Ordered prime signatures in the order of increasing smallest numbers of ordered prime signatures

## Orderings of rational integers

Cf. Orderings of rational integers

## Orderings of rational numbers

### Graded orderings of rational numbers

Cf. Graded orderings of rational numbers.

## Orderings of algebraic numbers

### Graded orderings of algebraic numbers

Cf. Graded orderings of algebraic numbers.

## See also

## External links

- Wikipedia, Lexicographical order.
- Wikipedia, Colexicographical order.
- Wikipedia, Monomial order.
- Wikiversity, Lexicographic and colexicographic order