A074683 Permutation of natural numbers induced by the Catalan Automorphism *A074683 acting on parenthesizations as encoded and ordered by A014486/A063171

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

Offset

0,3

Comments

This bijection maps between the "standard" ordering of binary trees as encoded by A014486 and "variant A quaternary encoding" as explained in the sequence A085184.

This is a rare example of Catalan Automorphism (with simple definition) where the cycle count sequence (A089411) is not monotone. (See A127296 for more complex example.)

Links

Table of n, a(n) for n=0..69.

A. Karttunen, Catalan Automorphisms

Index entries for sequences that are permutations of the natural numbers

Prog

(Scheme function implementing this automorphism on list-structures/S-expressions:) (define (*A074683! s) (cond ((pair? s) (*A074683! (car s)) (*A074683! (cdr s)) (*A074679! s))) s)

Crossrefs

Row 12 of A122202. Inverse of A074684. a(n) = A057163(A074682(A057163(n))).

The number of cycles, maximum cycle sizes and LCM's of all cycle sizes in subpermutations limited by A014137 and A014138 are given by A089411, A086586 and A089412.

Sequence in context: A130395 A131171 A057504 * A131004 A082357 A130357

Adjacent sequences: A074680 A074681 A074682 * A074684 A074685 A074686

Keyword

nonn

Author

Antti Karttunen, Sep 11 2002

Status

approved