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 "SPINE". In this recursion scheme the given automorphism is first applied at the root of binary tree, before the algorithm recurses down to the new right-hand side branch. The associated Scheme-procedures SPINE and !SPINE 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 A122204.

The recursion scheme SPINE has a well-defined inverse, that is, it acts as a bijective mapping on the set of all Catalan automorphisms. 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 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.)

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

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

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

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

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

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

That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.

This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122204 with the recursion scheme "SPINE", or equivalently row n is obtained as SPINE(ENIPS(n-th row of A089840)). 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 A122285. This table contains also all the rows of A122203 and A089840.

This automorphism converts lists of even length (1 2 3 4 ... 2n-1 2n) to the form ((1 . 2) (3 . 4) ... (2n-1 . 2n)) and when applied to lists of odd length, like (1 2 3 4 5), i.e. (1 . (2 . (3 . (4 . (5 . ()))))), converts them as ((1 . 2) . ((3 . 4) . (() . 5))).