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

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

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.

The signature-permutation of the automorphism which is derived from the seventeenth non-recursive automorphism *A074680 with recursion schema NEPEED (see A122284 for the definition).