cp's OEIS Frontend

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122203 with the recursion scheme "KROF", or equivalently row n is obtained as KROF(SPINE(n-th row of A089840)). See A122202 and A122203 for the description of KROF and SPINE. Moreover, each row of A122288 can be obtained as the "NEPEED" transform of the corresponding row in A122285. (See A122284 for the description of NEPEED). Each row occurs only once in this table. Inverses of these permutations can be found in table A122287. This table contains also all the rows of A122202 and A089840.

This automorphism of binary trees first swaps the left and right subtree of the root and then proceeds recursively to the (new) left subtree, to do the same operation there. This is one of those Catalan bijections which extend to a unique automorphism of the infinite binary tree, which in this case is A153142. See further comments there and in A153141.

This bijection, Knack, is a ENIPS-transformation of the simple swap: ENIPS(*A069770) (i.e., row 1 of A122204). Furthermore, Knack and Knick (the inverse, A069767) have a special property, that FORK and KROF transforms (explained in A122201 and A122202) transform them to their own inverses, i.e., to each other: FORK(Knick) = KROF(Knick) = Knack and FORK(Knack) = KROF(Knack) = Knick, thus this occurs also as row 1 in A122288 and naturally, the double-fork fixes both, e.g., FORK(FORK(Knack)) = Knack.

Note: the name in Finnish is "Naks".

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 "INORDER". In this recursion scheme the given automorphism is applied at the root of binary tree after the algorithm has recursed down the car-branch (the left hand side tree in the context of binary trees), but before the algorithm recurses down to the cdr-branch (the right 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 depth-first in-order traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures INORDER and !INORDER 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, *A089863 and *A129604 stay as they are. Inverses of these permutations can be found in table A130401.

Row n is the signature permutation of the Catalan automorphism which is obtained from A057163-conjugate of the n-th automorphism in the table A122203 with the recursion scheme "ENIPS", i.e. row n is obtained as ENIPS(A057163 o SPINE(A089840[n]) o A057163). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A130403. This table contains also all the rows of A122204 and A089840.

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 "RIBS".

In this recursion scheme the given automorphism is applied to all (toplevel) subtrees of the Catalan structure, when it is interpreted as a general tree. Permutations in this table form a countable group, which is isomorphic with the group in A089840. (The RIBS transformation gives the group isomorphism.)

Furthermore, row n of this table is also found as the row A123694(n) in tables A122203 and A122204. If the count of fixed points of the automorphism A089840[n] is given by sequence f, then the count of fixed points of the automorphism A089840[A123694(n)] is given by CONV(f,A000108) (where CONV stands for convolution) and the count of fixed points of the automorphism A122200[n] by INVERT(RIGHT(f)).

The associated Scheme-procedures RIBS and !RIBS can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism.

This sequence agrees with A025581 in its initial terms, but then diverges from it. - Antti Karttunen, May 11 2008

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122202 with the recursion scheme "KROF", or equivalently row n is obtained as KROF(KROF(n-th row of A089840)). See A122202 for the description of KROF. Each row occurs only once in this table. Inverses of these permutations can be found in table A122289.

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.

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122201 with the recursion scheme "FORK", or equivalently row n is obtained as FORK(FORK(n-th row of A089840)). See A122201 for the description of FORK. Each row occurs only once in this table. Inverses of these permutations can be found in table A122290.

Recursive transformation ENIPS for Catalan bijections has a well-defined inverse (see the definition & comments at A122204). For all Catalan bijections in A089840 that inverse produces a bijection which is itself in A089840. This sequence gives the indices to those positions where each ("primitive", non-recursive bijection) of A089840(n) occurs "atavistically" amongst the more complex recursive bijections in A122204. I.e. A122204(a(n)) = A089840(n). Similarly, other "atavistic forms" resurface as: A122287(a(n)) = A122201(n), A122286(a(n)) = A122203(n) and A122202(a(n)) = A122284(n). See also comments at A153833.

There exists similar atavistic index sequences computed for FORK (A122201) and KROF (A122202). Both start as 0,1654720,... (see A129604). This implies that regardless of how complex recursive derivations from A089840 one forms by repeatedly applying SPINE, ENIPS, FORK and/or KROF in some order (finite number of times), all the original primitive non-recursive elements of A089840 will eventually appear at some positions.

Other known terms: a(12)=65167, a(13)=65178, a(14)=65236, a(15)=169, a(16)=65302, a(22)-a(44) = 1656351, 1656576, 1656777, 1656628, 1656704, 1659507, 1659538, 1659653, 1659798, 1659685, 1659830, 1660155, 1660582, 1660439, 1660476, 1660621, 1660196, 1661073, 1660930, 1660859, 1661004, 1661287, 1661360.