|
%I #16 Apr 30 2018 10:56:02
%S 0,1,3,2,6,8,7,4,5,14,15,19,21,22,16,20,17,9,10,18,11,12,13,37,38,39,
%T 40,41,51,52,56,58,59,60,62,63,64,42,43,53,57,61,44,54,45,23,24,46,25,
%U 26,27,47,55,48,28,29,49,30,31,32,50,33,34,35,36,107,108,109,110,111
%N Permutation of natural numbers induced by Catalan Automorphism *A089858 acting on the binary trees/parenthesizations encoded by A014486/A063171.
%C 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.)
%C .....B...C.......B...A
%C ......\./.........\./
%C ...A...x...-->... .x...C...............A..().........()..A..
%C ....\./.............\./.................\./....-->....\./...
%C .....x...............x...................x.............x....
%C ((a . b) . c) -> ((b . a) . c) ______ (a . ()) ---> (() . a)
%C See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.
%H A. Karttunen, <a href="http://oeis.org/wiki/Catalan_Automorphisms">Catalan Automorphisms</a>
%H A. Karttunen, <a href="/A089408/a089408.c.txt">C-program for computing this sequence</a>
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations induced by Catalan automorphisms</a>
%o (Scheme functions implementing this automorphism on list-structures/S-expressions, both constructive (*A089858) and destructive (*A089858!) versions:)
%o (define (*A089858 s) (cond ((not (pair? s)) s) ((not (pair? (cdr s))) (cons (cdr s) (car s))) (else (cons (cons (cadr s) (car s)) (cddr s)))))
%o (define (*A089858! s) (cond ((pair? s) (cond ((pair? (cdr s)) (robl! s) (swap! (car s))) (else (swap! s))))) s)
%o (define (swap! s) (let ((ex-car (car s))) (set-car! s (cdr s)) (set-cdr! s ex-car) s))
%o (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))
%Y Row 13 of A089840. Inverse of A089861. a(n) = A072797(A069770(n)) = A069770(A089852(n)) = A057163(A073270(A057163(n))).
%Y Number of cycles: A073193. Number of fixed-points: A019590. Max. cycle size: A089422. LCM of cycle sizes: A089423 (in each range limited by A014137 and A014138).
%K nonn
%O 0,3
%A _Antti Karttunen_, Nov 29 2003
%E Further comments and constructive implementation of Scheme-function (*A089858) added by _Antti Karttunen_, Jun 04 2011
|
