cp's OEIS Frontend

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th nonrecursive automorphism in the table A089840 with the recursion scheme "ENIPS". In this recursion scheme the algorithm first recurses down to the right-hand side branch of the binary tree, before the given automorphism is applied at its root. This corresponds to the fold-right operation applied to the Catalan structure, interpreted e.g. as a parenthesization or a Lisp-like list, where (lambda (x y) (f (cons x y))) is the binary function given to fold, with 'f' being the given automorphism. The associated Scheme-procedures ENIPS and !ENIPS can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122203.

Because of the "universal property of folds", the recursion scheme ENIPS has a well-defined inverse, that is, it acts as a bijective mapping on the set of all Catalan automorphisms. Specifically, if g = ENIPS(f), then (f s) = (g (cons (car s) (g^{-1} (cdr s)))), that is, to obtain an automorphism f which gives g when subjected to recursion scheme ENIPS, we compose g with its own inverse applied to the cdr-branch of a S-expression (i.e. the right subtree in the context of binary trees). This implies that for any non-recursive automorphism f in the table A089840, ENIPS^{-1}(f) is also in A089840, which in turn implies that the rows of table A089840 form a (proper) subset of the rows of this table.

This sequence maps A000108(n) oriented (plane) rooted binary trees encoded in range [A014137(n-1)..A014138(n-1)] of A014486 to A001190(n+1) non-oriented rooted binary trees, encoded by their Matula-Goebel numbers (when viewed as a subset of non-oriented rooted general trees). See also the comments at A127301.

If the signature-permutation of a Catalan automorphism SP satisfies the condition A127302(SP(n)) = A127302(n) for all n, then it preserves the non-oriented form of a binary tree. Examples of such automorphisms include A069770, A057163, A122351, A069767/A069768, A073286-A073289, A089854, A089859/A089863, A089864, A122282, A123492-A123494, A123715/A123716, A127377-A127380, A127387 and A127388.

A153835 divides natural numbers to same equivalence classes, i.e. a(i) = a(j) <=> A153835(i) = A153835(j) - Antti Karttunen, Jan 03 2013

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C and D refer to arbitrary subtrees located on those nodes.)

.....B...C.....B...C...........A...B.............A...B...

......\./.......\./.............\./...............\./....

.......x...D.....x...D...........x...C.............x...C.

........\./.......\./.............\./...............\./..

.....A...x...-->...x...A...........x...D...-->...D...x...

......\./...........\./.............\./...........\./....

.......x.............x...............x.............x.....

This is the signature-permutation of Catalan automorphism which is derived from the automorphism *A123492 with the recursion schema KROF (defined in A122202). Like automorphisms *A057163 and *A069767/*A069768 these automorphisms are closed with respect to the subset of "zigzagging" binary trees (i.e., those binary trees where there are no nodes with two nonempty branches, or equivalently, those ones for which Stanley's interpretation (c) forms a non-branching line) and thus induce a permutation of binary strings. That is, starting from the root of such a binary tree, the turns taken by nonempty branches are interpreted as binary digits 0 or 1, depending on whether the tree grows to the left or right. In this manner, the Catalan automorphisms *A123494 and *A123493 induce the Binary Reflected Gray Code (see A003188 and A006068).

This is the signature-permutation of Catalan automorphism which is derived from nonrecursive Catalan automorphism *A123492 with the recursion schema SPINE (defined in A122203).