login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A089857
Permutation of natural numbers induced by Catalan Automorphism *A089857 acting on the binary trees/parenthesizations encoded by A014486/A063171.
14
0, 1, 2, 3, 4, 5, 8, 6, 7, 9, 10, 11, 12, 13, 21, 22, 19, 14, 15, 20, 16, 17, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 58, 59, 62, 63, 64, 56, 60, 51, 37, 38, 52, 39, 40, 41, 57, 61, 53, 42, 43, 54, 44, 45, 46, 55, 47, 48, 49, 50, 65, 66, 67, 68, 69, 70, 71, 72
OFFSET
0,3
COMMENTS
.A...B...........C...A
..\./.............\./
...x...C....-->....x...B...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . a) . b) _____ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.
PROG
(Scheme functions implementing this automorphism on list-structures/S-expressions, both constructive (*A089857) and destructive (*A089857!) versions:)
(define (*A089857 s) (if (and (pair? s) (pair? (car s))) (cons (cons (cdr s) (caar s)) (cdar s)) s))
(define (*A089857! s) (cond ((not (pair? s)) s) ((not (pair? (car s))) s) (else (swap! s) (robl! s) s)))
(define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) 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))
CROSSREFS
Row 11 of A089840. Inverse of A089855. a(n) = A074679(A069770(n)) = A069770(A089862(n)) = A057163(A089851(A057163(n))).
Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).
Sequence in context: A082351 A122319 A123714 * A122316 A130990 A131150
KEYWORD
nonn
AUTHOR
Antti Karttunen, Nov 29 2003
EXTENSIONS
Further comments and constructive implementation of Scheme-function (*A089857) added by Antti Karttunen, Jun 04 2011
STATUS
approved