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

These terms form a subgroup in A089840 (A089839). Because A127301 can be computed as a fold and most of the recursive derivations of A089840 (i.e., tables A122201-A122204, A122283-A122290, A130400-A130403) are also folds, this sequence also gives the indices to those derived tables where bijections preserving A127301 occur.

These elements form a subgroup in A089840 (A089839). Such elements consists of only such clauses where each vertex stays at the same distance from the root of the binary tree and in the image tree will still be sibling to its original sibling in the pre-image tree.

Because A127302 can be computed as a fold and most of the recursive derivations of A089840 (i.e. tables A122201-A122204, A122283-A122290, A130400-A130403) are also folds, this sequence gives also the indices to those derived tables where bijections preserving A127302 occur.

These elements form a subgroup in A089840 (A089839) isomorphic to a group consisting of all finitely iterated wreath products of the form S_2 wr S_2 wr ... wr S_2 and each is an image of some finitary automorphism of an infinite binary tree. E.g. A089840(1) = *A069770 is an image of the generator A of Grigorchuk Group. See comments at A153246 and A153141.

The defining properties are propagated by all recursive transformations of A089840 which themselves do not behave differently depending whether there are internal or terminal vertices in the neighborhood of any vertex (at least the ones given in A122201-A122204, A122283-A122290, A130400-A130403), so this sequence gives also the corresponding positions in those tables.

This bijection of binary trees can be obtained by applying bijection *A074679 to the right hand side subtree and leaving the left hand side subtree intact:

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

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

..B...x....-->....x...D.................B..().........()..B..

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

A...x...........A...x.................A...x.........A...x....

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

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

.............................................................

Note that the first clause corresponds to generator B of Thompson's groups F, T and V, while *A074679's first clause corresponds to generator A and furthermore, *A089851 corresponds to generator C and *A072796 to generator pi_0 of Thompson's group V. (To be checked: can Thompson's V be embedded in A089840 by using these or some other suitably chosen generators?)

Comment to above: I think now that it is a misplaced hope to embed V in A089840. Instead, it is more probable that Thompson's V is isomorphic to the quotient group A089840/N, where N is a subgroup of A089840 which includes identity (*A001477) and any other bijection (e.g. *A154126) that fixes all large enough trees. For more details, see my "On the connection of A089840 with ..." page. - Antti Karttunen, Aug 23 2012

These elements form a subgroup in A089840 (A089839).

This automorphism either swaps (if A057515(n) > 1) the first two toplevel elements (of a general plane tree, like *A072796 does) and otherwise (if n > 1, A057515(n)=1) swaps the sides of the left hand side subtree of the S-expression (when viewed as a binary tree, like *A089854 does). This is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.

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

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

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

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

...x....(A072796)....x....................x...(A089854)...x

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

This is the first multiclause automorphism in table A089840 which cannot be represented as a composition of two smaller nonrecursive automorphisms, the property which is also shared by *A123499 and *A123500.