User:Antti Karttunen/Catalania/Alternative Catalan Orderings

Note: because these orderings might feel more like my own personal research, I moved this whole section under my own namespace. - Antti Karttunen 12:13, 30 May 2017 (UTC)

Alternative Catalan Orderings

Apart from the usual ordering used in the sequence A014486, many Catalan structures lend them naturally to other methods of obtaining an 1-to-1 map with natural numbers. The following lists some of these methods, from simple to more complex ones involving ad hoc techniques.

Simple encodings of binary trees

The plane binary trees are easily ranked (i.e. mapped 1-to-1 to nonnegative integers) with any bijection $\scriptstyle b:\,\mathbb {N} _{0}\times \mathbb {N} _{0}\,\rightarrow \,\mathbb {N} _{0}\,$ by mapping an empty tree to zero, and any other tree to value $\scriptstyle 1+b(L,R)\,$, where $\scriptstyle L\,$ and $\scriptstyle R\,$ are recursively encoded values for the left and right hand side subtrees. Note: There are a lot's of such bijections in OEIS, just search for tables which are permutations of non-negative integers.

Arithmetic encoding of binary trees

With arithmetic encoding of binary trees, the empty tree maps to integer zero, and the recursively encoded left ($\scriptstyle L\,$) and right hand subtrees ($\scriptstyle R\,$) are combined as:

$(L~x~R)~=~1+((L+(L+R)^{2}+3R)/2).\,$

Note that $\scriptstyle ((L+(L+R)^{2}+3R)/2)\,$ is the bivariate formula for A001477 (in table form). See the sequences A071653 and A071654.

Reflected arithmetic encoding of binary trees

This is like above (arithmetic encoding of binary trees), except that the recursively encoded left ($\scriptstyle L\,$) and right hand subtrees ($\scriptstyle R\,$) are combined in the other order, as:

$(L~x~R)~=~1+((R+(R+L)^{2}+3L)/2).\,$

Note that $\scriptstyle ((R+(R+L)^{2}+3L)/2)\,$ is the bivariate formula for A061579 (in table form). See the sequences A071651 and A071652.

Recursive binary interleaving of binary trees

The Morton coding which is based on interleaving the binary representations of two (or more) natural numbers to produce a single natural number (see the sequences A000695, A059905 and A059906) can be naturally applied to binary trees, by interleaving the left hand and right hand side subtrees of a tree after they have been first recursively encoded in a similar fashion. (For a graphical explanation, see the sequences A082856 and A082857.) Note that in contrast to other encodings presented on this page, this mapping is not onto $\scriptstyle \mathbb {N} \,$, but instead, leaves many integers unused. However, taking the greatest common subtree and the least common supertree of any two trees can be implemented just with a bitwise AND or OR when using this encoding.

Encodings based on recursive factorization to constituents

The balanced paranthesizations (or any of the related intepretations: plane general trees, Dyck paths, totally balanced sequences, etc.) can be ranked to natural numbers also in other ways which are all based on various ways how a natural number (or nonnegative integer) can be recursively factored to a unique tuple of natural numbers (nonnegative integers).

Prime-exponent encoding of general trees/parenthesizations

Each natural number has a unique prime factorization, where each prime may occur zero or more times in the product. If we consider only the exponents of primes 2, 3, 5, ... (taken as zero for those primes which are not present in factorization) up to the largest prime factor of n (A006530$\scriptstyle (n)\,$), and add one to the exponent of each, except to the exponent of the largest prime present (which of course must have a strictly positive exponent), we will get a finite sequence ("tuple") of natural numbers $\scriptstyle (n_{1}~n_{2}~\dots ~n_{k})\,$. Note that 1 is mapped to an empty sequence, $\scriptstyle (~)\,$. By applying the same process recursively to each natural number in the sequence (until 1's are encountered and in turn converted to $\scriptstyle (~)\,$'s) one obtains a unique parenthesization from each natural number.

See the sequence A075166.

GF(2)[X]-factorization encoding of general trees/parenthesizations

This encoding works otherwise like above (prime-exponent encoding of general trees), but uses factorization of $\scriptstyle GF(2)[X]\,$ polynomials (which can conveniently be encoded as binary numbers) instead of prime factorization. This is possible because also $\scriptstyle GF(2)[X]\,$ polynomials form a unique factorization domain.

See the sequence A106456.

Binary runlength encoding of general trees/parenthesizations

This encoding of parenthesizations is based on run-length encoding. Each non-negative integer can be uniquely represented in binary system (see A007088). After 0, which is taken to correspond to an empty sequence $\scriptstyle (~)\,$, if we take only bits from the least significant bit to the most significant bit (which is always 1), and replace each maximal run of 0-bits (or respectively: 1-bits) with their count, and subtract one from that count, we will obtain a finite sequence ("tuple") of non-negative integers $\scriptstyle (n_{1}~n_{2}~\dots ~n_{k})\,$. By applying the same process recursively to each non-negative integer in the sequence (until 0's are encountered and in turn converted to $\scriptstyle (~)\,$'s) one obtains a unique parenthesization from each non-negative integer.

See the sequences A075168 & A075169. For a graphical explanation, see the sequence A075171.

More complex encodings of binary trees

These are like simple encodings of binary trees in that they use similar bijection $\scriptstyle b:\,\mathbb {N} \times \mathbb {N} \,\rightarrow \,\mathbb {N} \,$, with an empty tree mapped to zero, and any other tree to value $\scriptstyle 1+b(L,R)\,$. However, here there often has been an attempt to tailor the bijection $\scriptstyle b\,$ in such a way that the "locality" of ranking function would improve. (I.e., that "smallish trees" would map to "smallish integers" before "largish trees".)

Encoding of binary trees with triangle-stretching N X N → N bijection

Here the bijection $\scriptstyle b\,$ is a bivariate function A072734 (that is, a table), which has been constructed in such a way, that it is "sending" smaller values from the top of "default triangle" (see A001477 in table form) down to its edges, while substituting larger values coming from down below at center parts up to the top. (Imagine a volcano that has erupted lava on its flanks, from its central crater.)

See the sequences A072787 and A072788.

Binary tree encoding with bijection

We can employ also a bivariate form of A054238 as our bijection $\scriptstyle b\,$.

See the sequences A072634 and A072635.

Binary tree encoding with a composition of bijections

Here the composition A048680 $\scriptstyle ~o~\,$ A054238 is employed as the bijection $\scriptstyle b\,$. The idea is a bit similar as when using A072734: The permutation A048680 will "penalize" any integers with many 1-bits, by making them larger, while it will "favor" integers with a few 1-bits, by making them smaller.

See the sequences A072656 and A072657.

Source code

Scheme code for computing these sequences should be selected and collected to one place. Meanwhile, you can peruse my old collection of Scheme sources for these sequences at:

• https://github.com/karttu/IntSeq/tree/master/src/Uncleaned/Catalania

Authorship

Extracted this page from a section of Orderings of combinatorial interpretations of Catalan numbers page in May 30 2017.

Cite this page as

A. Karttunen, <a href="http://oeis.org/wiki/User:Antti_Karttunen/Catalania/Alternative_Catalan_Orderings">Alternative Orderings of Combinatorial interpretations of Catalan numbers</a>, OEIS Wiki.