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

Author

Antti Karttunen, Sep 11 2002

Keywords

• nonn

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

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

Extensions

Description clarified Oct 10 2006