This site is supported by donations to The OEIS Foundation.

User:Antti Karttunen/Catalan bijections

From OeisWiki
Jump to: navigation, search

Note: This page is currently a stub to be linked to from all the "Catalan automorphism" related-sequences, signature permutations, etc. For the perplexed, everything will be explained here, how to generate the signature-permutations, and so on. Meanwhile, please refer to unfinished draft.[1]

Note 2: I moved this page under my own namespace August 31 2012, as the topic concerns mostly my original research, and the page will stay in its current unfinished shape quite long. I will move this back to the "public namespace", when the page is in better shape and on more firm footing. However, you are still welcome to edit it, if you have an important point or correction to add! Eventually, when it is edited to better shape, and everything is on more firm footing, it will be moved back to the "public namespace" of OEIS Wiki.

This article is under construction.            

Please do not rely on any information it contains.            


Catalan bijection, as used in this article, refers to any bijection on any combinatorial interpretation of Catalan numbers that preserves the size of a structure. That is, we require only that, say, a plane binary tree of n nodes is mapped to a plane binary tree of the same size.

Note that this shouldn't confused with the bijections asked by Stanley in his Catalan exercises[2] as those bijections map between different interpretations, and should probably more accurately be called isomorphisms instead.

Catalan automorphisms

Many Catalan bijections can be shown to be symmetry operations (mainly reflections and rotations) of some of the combinatorial interpretations of Catalan numbers. However, it should be noted, that although currently most of the signature permutations present in OEIS use the term "automorphism" instead of "bijection" (almost all apart from the identity permutation (A001477) submitted by Antti Karttunen, as of 19 July 2012), only for a few of them it is obvious to see that they clearly are in the strict sense automorphisms of some combinatorial interpretation of Catalan numbers, in a sense that they would preserve some structure (apart from simply preserving the size), and furthermore, partition the set of Catalan structures into different equivalence classes according to a well-defined structural criteria.

(Expert opinion on this topic requested, see Talk page).

Different ways to classify Catalan bijections

Because the group of all Catalan bijections is uncountable[3], there cannot be any scheme to list them all.


Nonrecursive bijections of binary trees

Nonrecursive bijections of binary trees, or somewhat loosely, nonrecursive Catalan automorphisms/bijections, are Catalan bijections whose action on rooted plane binary trees is constrained in such a way, that changes (i.e. permutations exchanging different subtrees) will occur only up to a definite distance from the root vertex. In other words, there is no unlimited recursion down to indefinite distances from the root, even with binary trees whose size approaches infinity. Note that here nonrecursive doesn't refer to recursive sets or recursive enumerability but concretely to structural recursion inherent in the structure of binary trees.

The composition of two nonrecursive bijections of binary trees is itself a nonrecursive bijection of binary tree, and likewise for the inverses of such bijections, thus they from a subgroup of all Catalan bijections. Each nonrecursive bijection of binary trees can be represented as a disjunction of clauses[4]. Each clause transforms the shape of the argument tree nonrecursively (with only finite number of subtrees exchanging their location), and the later clauses in disjunction are activated only if none of the preceding clauses matched to the argument tree, shapewise. As there are only finite number of clause-combinations whose total size sums to any given finite value, all such nonrecursive bijections can be listed, and the group they form is thus countable.

The signature permutations of the elements of that group can be found as the rows of the table A089840, starting from the simplest one, the trivial identity permutation A001477.

Recursive transformations of nonrecursive bijections of binary trees

From each nonrecursive bijection of binary trees, various further bijections can be formed by applying different recursive transformations of binary tree bijections to them, possibly multiple times. Signature permutations of such, "recursive, but simple" bijections can be found from tables A122200, A122201, A122202, A122203, A122204, A122283, A122284, A122285, A122286, A122287, A122288, A122289, A122290, A130400-A130403, etc.

Notably, many symmetry operations of various interpretations, and other important Catalan bijections belong to this inductively defined subset of bijections.

Other, still larger sets of bijections

After having fixed a finite set of recursive transformation operations with which to derive further bijections from the nonrecursive set in A089840, the next question is whether also all compositions of the said bijections are included in such an inductively built set.

Furthermore, one day there might be found a new formalism for enumerating, that will admit a larger set of bijections.


Complex Catalan bijections

These are bijections which author conjectures to be out of reach from any of the above presented finite inductive construction process (starting from any nonrecursive bijection of the binary trees in A089840). Some examples are Meeussen's breadth-first<—>depth-first conversion bijections, for binary trees A057117/A057118 and for general trees A072088/A072089, Kreweras' 1970 involution on Dyck paths, A125976 (most probably), Elizalde's and Deutsch's 2003 bijection for Dyck paths, A127291/A127292, although actually called "simple" in the defining paper[5].

Notes and references

  1. A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections, unfinished draft, version of 26 July 2011.
  2. R. P. Stanley, Exercises on Catalan and Related Numbers, excerpted from Enumerative Combinatorics, vol. 2, version of 23 June 1998.
  3. This is easy to see if one ranks each sub-permutation (limited by A014137 and A014138) of a signature permutations with some ranking function for permutations to obtain from each possible signature permutation an infinite "decimal" number whose nth digit after "decimal point" can range from 0 to A000142(A000108(n))-1, and then apply Cantor's diagonal argument.
  4. http://oeis.org/A089840/a089840p.txt
  5. Emeric Deutsch and Sergi Elizalde, A simple and unusual bijection for Dyck paths and its consequences, Annals of Combinatorics, 7 (2003), no. 3, 281-297.

Authorship

The first version of this page was written by Antti Karttunen 23:05, 20 June 2011 (UTC)

Cite this page as

A. Karttunen et al, <a href="http://oeis.org/wiki/Catalan_bijections">Catalan bijections</a>, a page in the OEIS Wiki.