Gatomorphisms: Collection of Automorphisms acting on parenthesizations (and other structures in Catalan families).

Scheme source files:

gatomain.scm

The "main module" which loads the other ones.

gatorank.scm

Functions for ranking & unranking the totally balanced binary sequences, and converting them to parenthesizations.

gatoaltr.scm

Functions for "alternative ranking schemes" (concerns you if you came here from one of the "Catalan reranking" or related sequences. Still to be transferred to the page of its own...).

gatomorf.scm

Collection of hand-coded gatomorphisms.

gatosiga.scm

Code for producing infinite number of "Simple Gatomorphisms of Type B" automatically. The table A073200 is computed with this module.

gatocout.scm

Functions for converting parenthesizations to other incarnations of the Catalan families, like polygon triangularizations, non-crossing chord arrangements (i.e. fixed-point free involutions), etc. An auxiliary module for the next one.

gato-fps.scm

Module for printing the effects of gatomorphisms as Postscript-files. Runs in Scsh and requires FPS-package.

gatochek.scm

Auxiliary functions for printing a check-list as a HTML-file.

../Schemuli/intfuns1.scm

A collection of integer functions (factorial, binomial, Catalans, etc.), some needed by gatorank.scm

../Schemuli/definech.scm

A hygienic definition for the macro definec used by the above module and gatorank.scm. Use this with the releases >= 7.7.0 of MIT Scheme.

../Schemuli/definecd.scm

The old "dirty" definition for the same macro definec. Use this with the releases < 7.7.0 of MIT Scheme.

../Schemuli/lstfuns1.scm

A collection of needed list manipulation and other functions (attach!, cons2top!, copy-tree, nthcdr, count-pars, etc)

Some definitions:

Gatomorphism

Gatomorphism is any bijection from a set of parenthesizations of the size n to the same set (of size n), which is well-defined for all the sizes n>=0 (for sizes n=0 and 1 we have an identity mapping). In place of parenthesizations we can assume that it acts on any other manifestation of the exercise 19 by Stanley. The plane binary trees and plane general trees are also commonly referred to in our examples.

Lukasiewicz-word permuting

We say that a gatomorphism g is Lukasiewicz-word permuting if the Lukasiewicz-word of g(s) is a permutation of the Lukasiewicz-word of s for all possible general trees/parenthesizations s. This implies that the subset of the planar binary trees (*) (of the general trees) is closed under the action of g, and thus its restriction to that subset induces another gatomorphism. The table below gives the correspondence between various Lukasiewicz-word permuting gatomorphisms and the gatomorphisms induced by their restriction to the subset of the plane binary trees.

Note: The same comment applies of course also to the subset of unary-binary trees, with max. branching degree=2, enumerated by the Motzkin numbers.

Telescoping

We say that a gatomorphism g is "telescoping" (I used previously the term "self-embeddable") if for all the totally balanced binary sequences s in A014486 (A063171) it holds that g(10.s) = 10.g(s). (Here . denotes the juxtaposition, and 10 is a binary prefix concatenated of one 1-bit and one 0-bit).
This is equivalent to saying that each sub-permutation of the length A000108(n) induced by g's action on the standard sequence of lexicographically ordered parenthesizations A014486 (A063171) starts with the same cycle-structure as the previous sub-permutation. In this case we can form yet another permutation of the natural numbers by conceptually taking the "infiniteth" of such sub-permutations and by "normalizing" it to begin from 0 or 1.

Note that if g(1.s.0) = 1.g(s).0 holds, then the car/cdr-flipped conjugate of the gatomorphism g is a telescoping one. For example, it is easy to see that this holds for the gatomorphism DeepReverse (and similarly for DeepRotates), and as A069787 = A057163 o A057164 o A057163, we can contract A069787 to get A072799.

Table of some gatomorphisms, and their relations.

Samples/Images/etc.:

a014486.ps

This 63-page postscript-file produced with the module gato-fps.scm shows the sequence A014486 upto the size n=7 (with total of 626 structures) in the following formats

• (i) (ordinary Dyck paths),
• (e) (plane trees with n+1 vertices),
• (d) (plane binary trees with 2n+1 vertices (or n+1 endpoints)),
• (a) (triangulations of a convex (n+2)-gon into n triangles by n-1 diagonals that do not intersect in their interiors) and
• (n) (n nonintersecting chords joining 2n points on the circumference of a circle, i.e. non-crossing handshakes arrangements)

given in the Stanley's exercise 19 on the chapter Exercises on Catalan and Related Numbers of his book Enumerative Combinatorics, vol. 2.

a014486_1.jpg

The first page of the above postscript-file saved as a JPEG-image.

• Henry Baker, Linear Logic and Permutation Stacks -- The Forth Shall Be First (Some inspiration.)
• David Boozer, Primitive Recursive Functions (As well, for the "Simple Gatomorphisms of Type B")
• R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90. (Concerned with the gatomorphisms A057505 & A057506 and their powers.)
• R. K. Guy, Catwalks, Sandsteps and Pascal Pyramids, J. Integer Seqs., Vol. 3 (2000), #00.1.6)
• Chris Hanson, Chapter 7 from the MIT Scheme Reference Manual (Explains the car, cdr and cons. The Scheme list structure)
• Nikos K., Kritikós Agriógatos - the Cretan wild cat
• A. Karttunen, Catalan's Triangle and ranking of Dyck paths, etc.
• N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences.
• R. P. Stanley, Exercises on Catalan and Related Numbers