A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

0, 1, 3, 2, 6, 7, 8, 4, 5, 14, 15, 16, 17, 18, 19, 20, 21, 9, 10, 22, 11, 12, 13, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 23, 24, 59, 25, 26, 27, 60, 61, 62, 28, 29, 63, 30, 31, 32, 64, 33, 34, 35, 36, 107, 108, 109, 110, 111

Offset

0,3

Comments

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.

Links

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

A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections, (an unfinished draft)

A. Karttunen, Notes on the orbits of this permutation, OEIS Wiki.

A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive bijections of oriented binary trees

Index entries for signature-permutations of Catalan automorphisms

Prog

(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))

Crossrefs

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 because 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)] of this permutation).

Sequence in context: A100280 A268827 A092745 * A122323 A123495 A130369

Adjacent sequences: A074676 A074677 A074678 * A074680 A074681 A074682

Keyword

nonn

Author

Antti Karttunen, Sep 11 2002, description clarified Oct 10 2006.

Status

approved