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)
- 1 Alternative Catalan Orderings
- 1.1 Simple encodings of binary trees
- 1.2 Encodings based on recursive factorization to constituents
- 1.3 More complex encodings of binary trees
- 2 Source code
- 3 Notes
- 4 Authorship
- 5 Cite this page as
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 by mapping an empty tree to zero, and any other tree to value , where and 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 () and right hand subtrees () are combined as:
Reflected arithmetic encoding of binary trees
This is like above (arithmetic encoding of binary trees), except that the recursively encoded left () and right hand subtrees () are combined in the other order, as:
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 , 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), 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 . Note that 1 is mapped to an empty sequence, . By applying the same process recursively to each natural number in the sequence (until 1's are encountered and in turn converted to '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 polynomials (which can conveniently be encoded as binary numbers) instead of prime factorization. This is possible because also 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 , 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 . By applying the same process recursively to each non-negative integer in the sequence (until 0's are encountered and in turn converted to 's) one obtains a unique parenthesization from each non-negative integer.
More complex encodings of binary trees
These are like simple encodings of binary trees in that they use similar bijection , with an empty tree mapped to zero, and any other tree to value . However, here there often has been an attempt to tailor the bijection 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 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.)
Binary tree encoding with bijection
We can employ also a bivariate form of A054238 as our bijection .
Binary tree encoding with a composition of bijections
Here the composition A048680 A054238 is employed as the bijection . 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.
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:
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.