cp's OEIS Frontend

This automorphism is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.

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

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

...x...C....-->....A...x............()..x......-->......x..().

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

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

((a . b) . c) --> (a . (b . c)) / (() . (b . c)) --> ((c . b) . ())

This automorphism cannot be represented as a composition of two smaller nonrecursive automorphisms. Cf. A123503.

The number of orbits to which the corresponding automorphism(s) partitions the set of A000108(n) binary trees with n internal nodes.

Each row is a permutation of natural numbers and occurs only once. The table is closed with regards to the composition of its rows (see A089839) and it contains the inverse of each (their positions are shown in A089843). The permutations in table form an enumerable subgroup of the group of all size-preserving "Catalan bijections" (bijections among finite unlabeled rooted plane binary trees). The order of each element is shown at A089842.

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 automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).

.A...B...............B...A

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

...x...C...-->.....C...x...............()..A.........A..()..

....\./.............\./.................\./....-->....\./...

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

((a . b) . c) --> (c . (b . a)) __ (() . a) ----> (a . ())

See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

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

.A...B...........B...A

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

...x...C....-->....x...C...............()..A.........()..A..

....\./.............\./.................\./....-->....\./...

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

((a . b) . c) -> ((b . a) . c) ___ (() . a) ---> (() . a)

In terms of S-expressions, this automorphism swaps caar and cdar of an S-exp if its first element is not ().

See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

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

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 "REDRONI". In this recursion scheme the given automorphism is applied at the root of binary tree after the algorithm has recursed down the cdr-branch (the right hand side tree in the context of binary trees), but before the algorithm recurses down to the car-branch (the left hand side of the binary tree, with respect to the new orientation of branches, possibly changed by the applied automorphism). I.e. this corresponds to the reversed depth-first in-order traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures REDRONI and !REDRONI can be used to obtain such a transformed automorphism from any constructively (or respectively: destructively) implemented automorphism. Each row occurs only once in this table and similar notes as given e.g. for table A122202 apply here, e.g. the rows of A089840 all occur here as well. This transformation has many fixed points besides the trivial identity automorphism *A001477: at least *A069770, *A089859 and *A129604 stay as they are. Inverses of these permutations can be found in table A130400.

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

...B...C...........C...B

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

.A...x....-->....A...x.................A..().........A...()..

..\./.............\./...................\./....-->....\./...

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

(a . (b . c)) -> (a . (c . b)) ____ (a . ()) ---> (a . ())

In terms of S-expressions, this automorphism swaps cadr and cddr of an S-exp if its length > 1.

Look at the example in A069770 to see how this will produce the given sequence of integers.

This "Catalan bijection" effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)

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

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

...x...x....-->..x...x.......()..x..-->..()..x...........x..()...-->..x..().

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

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

i.e. we apply A069770 (that is, the corresponding automorphism) both to the left and right subtree of a binary tree and fix both the empty tree and the tree of one internal node.