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 "FORK". In this recursion scheme the given automorphism is first applied at the root of binary tree, before the algorithm recurses down to the both branches (new ones, possibly changed by the given automorphism). I.e. this corresponds to the pre-order (prefix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures FORK and !FORK 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 A122202.

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 "NEPEED". In this recursion scheme the algorithm first recurses down to all subtrees, before the given automorphism is applied at the root of general tree. I.e., this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a general tree. The associated Scheme-procedures NEPEED and !NEPEED 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 A122283.

The recursion scheme KROF (described in A122202) is equivalent to a composition of recursion schemes ENIPS (described in A122204) and NEPEED, i.e., KROF(f) = NEPEED(ENIPS(f)) holds for all Catalan automorphisms f. Because of the "universal property of folds", these recursion schemes have well-defined inverses, that is, they are bijective mappings on the set of all Catalan automorphisms. Thus we can equivalently define that NEPEED(f) = KROF(ENIPS^{-1}(f)). 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 A122284 form a (proper) subset of the rows of table A122202. E.g., row 1 of A122284 is row 15 of A122202, row 2 of A122284 is row 3617 of A122202, row 12 of A122284 is row 65167 of A122202, row 15 of A122284 is row 169 of A122202. - Antti Karttunen, May 25 2007

The recursion scheme FORK (described in A122201) is equivalent to a composition of recursion schemes SPINE (described in A122203) and DEEPEN, i.e., FORK(f) = DEEPEN(SPINE(f)) holds for all Catalan automorphisms f. These recursion schemes have well-defined inverses, that is, they are bijective mappings on the set of all Catalan automorphisms. Thus we can equivalently define that DEEPEN(f) = FORK(SPINE^{-1}(f)). Specifically, if g = SPINE(f), then (f s) = (cond ((pair? s) (let ((t (g s))) (cons (car t) (g^{-1} (cdr t))))) (else s)) that is, to obtain an automorphism f which gives g when subjected to recursion scheme SPINE, we compose g with its own inverse applied to the cdr-branch of a S-expression. This implies that for any non-recursive automorphism f in the table A089840, SPINE^{-1}(f) is also in A089840, which in turn implies that the rows of table A122283 form a (proper) subset of the rows of table A122201. E.g., row 1 of A122283 is row 21 of A122201, row 2 of A122283 is row 3613 of A122201, row 17 of A122283 is row 65352 of A122201, row 21 of A122283 is row 251 of A122201. - Antti Karttunen, May 25 2007

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

This automorphism of binary trees first swaps the left and right subtree of the root and then proceeds recursively to the (new) right 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 A153141. See further comments there.

This bijection, Knick, is a SPINE-transformation of the simple swap: SPINE(*A069770) (i.e., row 1 of A122203). Furthermore, Knick and Knack (the inverse, *A069768) 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 a row 1 in A122287 and naturally, the double-fork fixes both, e.g., FORK(FORK(Knick)) = Knick. There are also other peculiar properties.

Note: the name in Finnish is "Niks".

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.

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.

This is a rare example of Catalan Automorphism (with simple definition) where the cycle count sequence (A089411) is not monotone. (See A127296 for more complex example.)

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.

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.

Recursive transformation SPINE for Catalan bijections has a well-defined inverse (see the definition & comments at A122203). 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 A122203. I.e. A122203(a(n)) = A089840(n). Similarly, other "atavistic forms" resurface as: A122288(a(n)) = A122202(n), A122285(a(n)) = A122204(n) and A122201(a(n)) = A122283(n). See also comments at A153832.

Other known terms: a(17)-a(44): 65352, 65359, 65604, 65739, 251, 1656303, 1656426, 1656552, 1656628, 1656479, 1661655, 1661816, 1666720, 1684006, 1684221, 1667042, 1667007, 1684152, 1661799, 1661676, 1666759, 1684081, 1684437, 1667151, 1684509, 1667187, 1661961, 1661944.