Orderings

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

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

Orderings of the 3-element subsets of $\scriptstyle \{1,2,3,4,5,6\}\,$ mentioned in the following sections. When the subsets are ordered the corresponding binary vectors are ordered as well.

Orderings of the 24 permutations of $\scriptstyle \{1,2,3,4,5\}\,$ that have a complete 5-cycle The inversion vectors of permutations in CoLex order are in RevCoLex order and vice versa.

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 $\scriptstyle A\,$ and $\scriptstyle B\,$, the lexicographical order on the Cartesian product $\scriptstyle A\times B\,$ is defined as

$(a,b)\leq _{A\times B}^{\rm {lex}}(a^{\prime },b^{\prime }){\rm {~if~and~only~if~}}a<_{A}a^{\prime }{\rm {~or~}}(a=_{A}a^{\prime }{\rm {~and~}}b\leq _{B}b^{\prime }).\,$

The result is a partial order. If $\scriptstyle A\,$ and $\scriptstyle B\,$ are totally ordered sets, then the result is a total order as well.

One can define the lexicographic order on the Cartesian product of $\scriptstyle n\,$ ordered sets.

Suppose

$\{A_{1},A_{2},\cdots ,A_{n}\}$

is an $\scriptstyle n\,$-tuple of sets, with respective total orderings

$\{<_{1},<_{2},\cdots ,<_{n}\}.$

The lex ordering is then

$(a_{1},a_{2},\dots ,a_{n})<_{A_{1}\times A_{2}\times \cdots \times A_{n}}^{\rm {lex}}(b_{1},b_{2},\dots ,b_{n})\iff (\exists \ m>0)\ (\forall \ i<m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m}).$

The following is a lex ordering on subsets of size 3 from the set $\scriptstyle \{1,2,3,4,5,6\}\,$:

$123<124<125<126<134<135<136<145<146<156<234<235<236<245<246<256<345<346<356<456\,$

More generally, one can define the lexicographic order on the Cartesian product of $\scriptstyle n\,$ 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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$456<356<346<345<256<246<245<236<235<234<156<146<145<136<135<134<126<125<124<123\,$

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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$321<421<521<621<431<531<631<541<641<651<432<532<632<542<642<652<543<643<653<654\,$

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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$654<653<643<543<652<642<542<632<532<432<651<641<541<631<531<431<621<521<421<321\,$

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 $\scriptstyle A\,$ and $\scriptstyle B\,$, the colexicographical order on the Cartesian product $\scriptstyle A\times B\,$ is defined as

$(a,b)\leq _{A\times B}^{\rm {colex}}(a^{\prime },b^{\prime }){\rm {~if~and~only~if~}}b<_{B}b^{\prime }{\rm {~or~}}(b=_{B}b^{\prime }{\rm {~and~}}a\leq _{A}a^{\prime }).\,$

The result is a partial order. If $\scriptstyle A\,$ and $\scriptstyle B\,$ are totally ordered, then the result is a total order also.

One can define the colexicographic order on the Cartesian product of $\scriptstyle n\,$ ordered sets.

Suppose

$\{A_{1},A_{2},\cdots ,A_{n}\}$

is an $\scriptstyle n\,$-tuple of sets, with respective total orderings

$\{<_{1},<_{2},\cdots ,<_{n}\}.$

The colex ordering is then

$(a_{1},a_{2},\dots ,a_{n})<_{A_{1}\times A_{2}\times \cdots \times A_{n}}^{\rm {colex}}(b_{1},b_{2},\dots ,b_{n})\iff (\exists \ m>0)\ (\forall \ i>m)(a_{i}=b_{i})\land (a_{m}<_{m}b_{m}).$

The following is a colex ordering on subsets of size 3 from the set $\scriptstyle \{1,2,3,4,5,6\}\,$:

$123<124<134<234<125<135<235<145<245<345<126<136<236<146<246<346<156<256<356<456\,$

More generally, one can define the colexicographic order on the Cartesian product of $\scriptstyle n\,$ 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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$456<356<256<156<346<246<146<236<136<126<345<245<145<235<135<125<234<134<124<123\,$

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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$321<421<431<432<521<531<532<541<542<543<621<631<632<641<642<643<651<652<653<654\,$

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 $\scriptstyle \{1,2,3,4,5,6\}\,$:

$654<653<652<651<643<642<641<632<631<621<543<542<541<532<531<521<432<431<421<321\,$

Orderings of partitions

Graded orderings of partitions

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

Cf. Orderings of partitions.

Orderings of compositions

Graded orderings of compositions

The compositions of nonnegative integers $\scriptstyle n\,$ may be sorted with a graded ordering, where we first order by increasing $\scriptstyle n\,$ (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 $\scriptstyle n\,$ are usually sorted in graded reflected colexicographic order, i.e. graded by increasing $\scriptstyle \Omega (n)\,$, then by reflected colexicographic order of exponents (which nicely sorts by increasing $\scriptstyle \omega (n)\,$). With this convention, the prime signature internal order has the exponents in increasing order.

The prime signatures of positive integers $\scriptstyle n\,$ may also be sorted in graded colexicographic order, i.e. graded by increasing $\scriptstyle \Omega (n)\,$, then by colexicographic order of exponents (which nicely sorts by increasing $\scriptstyle \omega (n)\,$).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 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

• Orderings of partitions
• Orderings of compositions

• Orderings of prime signatures
• Orderings of ordered prime signatures

• Orderings of rational integers
• Orderings of rational numbers
• Orderings of algebraic numbers

External links

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