0,3

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-1)] of this permutation is given by A001683(n+1), i.e. the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. This is true because this automorphism traces "step-by-step" the rotation of Eulerian polygon triangulations effected by the latter automorphisms, but in one node larger context.

A. Karttunen, paper in preparation, draft available by e-mail.

A. Karttunen, Table of n, a(n) for n = 0..2055

A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.

Index entries for signature-permutations of Catalan automorphisms

(Scheme implementations of this automorphism. These act on S-expressions, i.e. list-structures:)

(CONSTRUCTIVE VERSION:) (define (*A074679 s) (cond ((not (pair? s)) s) ((pair? (cdr s)) (cons (cons (car s) (cadr s)) (cddr s))) (else (cons (cdr s) (car s)))))

(DESTRUCTIVE VERSION:) (define (*A074679! s) (cond ((pair? s) (cond ((pair? (cdr s)) (robl! s)) (else (swap! s))))) s)

(define (robl! s) (let ((ex-car (car s))) (set-car! s (cddr s)) (set-cdr! (cdr s) ex-car) (swap! (cdr s)) (swap! s) s))

(define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))

This automorphism has several variants, where the first clause is same (rotate binary tree to the left, if possible), but something else is done (than just swapping sides), in case the right hand side is empty: A082335, A082349, A123499, A123695. The following automorphisms can be derived recursively from this one: A057502, A074681, A074683, A074685, A074687, A074690, A089865, A120706, A122321, A122332. See also somewhat similar ones: A069773, A071660, A071656, A071658, A072091, A072095, A072093.

Inverse: A074680. Row 12 of A089840. Occurs also in A073200 as row 557243 as a(n) = A073283(A073280(A072796(n))). a(n) = A083927(A123498(A057123(n))).

Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n-1)] of this permutation).

Sequence in context: A006042 A100280 A092745 this_sequence A122323 A123495 A130369

Adjacent sequences: A074676 A074677 A074678 this_sequence A074680 A074681 A074682

nonn

Antti Karttunen (His-Firstname.His-Surname(AT)gmail.com), Sep 11 2002, description clarified Oct 10 2006.