This site is supported by donations to The OEIS Foundation.
User:Antti Karttunen/Speculations/Enumeration system for simple Catalan bijections
Note: this page belongs my series of "unfinished speculatory notes". The original version was a part of my application for Wolfram Research's Pisa 2009 NKS Summer School.
Goal
Develop a good enumeration formalism for all "simple" bijections on binary trees.
Here a "simple bijection of binary tree" means anything that can essentially implemented as a Lisp/Scheme-function that can examine any branch of the binary tree (given as an argument) in turn, and depending on which of the vertices are leaves (i.e. nil symbols) and which are internal vertices (cons cell pairs), take different actions, possibly calling itself recursively, or any other such bijection defined in a similar way. However, there would be no explicit support for any auxiliary data structures like an extra stack (apart the implicit one which enables the recursion) or a queue, for storing sub-trees of the argument tree, apart from what can be coded by using, say, some branch of the argument tree itself as a such temporary container.
Requirements
Foremost, the formalism should be able to represent all the elements in A089840 as well as in its recursively derived tables A122200-A122204, A122283-A122290 and A130400-A130403. Also, it should be possible to express co-recursive cases such as this one, implementing Callan's 2006 bijection[1]:
(define (*A127378! s) (cond ((null? s)) ((null? (cdr s)) (*A069770! s) (*A127378! (cdr s))) ((null? (car s)) (*A069770! s) (*A127380! (car s))) (else (*A127380! s)) ) s ) (define (*A127380! s) (for-each *A127378! s) s)
as well as (here the co-recursive bijections are inverses to each other):
(define (*A120705! s) (cond ((pair? s) (*A074680! s) (*A120705! (car s)) (cond ((pair? (cdr s)) (*A120705! (cddr s)) (*A120706! (cadr s)) ) ) ) ) s ) (define (*A120706! s) (cond ((pair? s) (*A074679! s) (*A120706! (cdr s)) (cond ((pair? (car s)) (*A120706! (caar s)) (*A120705! (cdar s)) ) ) ) ) s )
Note that this latter condition implies that also all the elements of the automorphism group would be included.
Also, the formalism should be able to define such "hybrid" nonrecursive/recursive bijections as *A082335 and its inverse *A082336.
However, the formalism doesn't need to be able to express such complex bijections as 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), Vaille's 1997 bijection on 'bridges' (Dyck paths), A125985, or Elizalde's and Deutsch's 2003 bijection for Dyck paths, A127291/A127292[2].
Whether it would be possible to define even 180 degree rotation of non-crossing handshakes, A069771, I am not sure. Thus, actually, this would give us a lots of nice research projects, to find the limits of expressibility of such a formalism.
One starting point for such a formalism might be the wreath recursion as defined e.g. in Bondarenko, Grigorchuk, et al. in[3], but extending it in such a way, that it can take different "recursion paths" depending on the vicinity of leaves, and where, instead of just an option of either fixing or swapping the subtrees at any given state, any possible "simple bijection" could be applied at that point, as either PRE-, IN- or POST-ORDER traversal in respect to the branches recursed. (E.g. this would be similar to how primitive recursive functions can be inductively constructed with just the operators of "composition" and "recursive composition", starting from a simple successor and projection functions.) In this case, the "basis elements", from which the induction starts, would be the non-recursive bijections (i.e. A089840), or some subset of them, if it can be proved to be of the same expressive power.
In any case, we should need to find a good tradeoff between the expressive power/generality vs. redundancy, also taking care that the formalism allots "small enough" indices for many important and interesting bijections (what I would call "practical enumerability").
References
- ↑ D. Callan, A bijection on Dyck paths and its cycle structure, The Electronic Journal of Combinatorics, 14(1), Article R28, 2007 (20pp). For on-line copy, see http://www.stat.wisc.edu/~callan/papers/Dyck_bijection/
- ↑ 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.
- ↑ http://arxiv.org/abs/0803.3555 Classification of groups generated by 3-state automata over a 2-letter alphabet