%I #6 Mar 31 2012 13:21:12
%S 0,1,3,2,6,7,8,5,4,14,15,16,17,18,19,20,21,12,13,22,11,9,10,37,38,39,
%T 40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,31,32,59,34,
%U 35,36,60,61,62,30,33,63,28,23,24,64,29,25,26,27,107,108,109,110,111
%N Signature permutation of a nonrecursive Catalan automorphism: rotate a binary tree left if possible, otherwise apply *A089863.
%C This automorphism is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.
%C ...B...C...............A...B...........A...B.............B...A
%C ....\./.................\./.............\./...............\./.
%C .A...x........-->........x...C...........x..()...-->...()..x..
%C ..\./.....................\./.............\./...........\./...
%C ...x.......................x...............x.............x....
%C (a . (b . c)) --> ((a . b) . c) / ((a . b) . ()) --> (() . (b . a))
%C This automorphism cannot be represented as a composition of two smaller nonrecursive automorphisms. Cf. A123503.
%H A. Karttunen, <a href="/A089840/a089840p.txt">Prolog-program which illustrates the construction of this and other similar nonrecursive Catalan automorphisms.</a>
%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%o (Scheme function, destructive implementation of this automorphism acting on S-expressions:) (define (*A123499! s) (cond ((null? s) s) ((pair? (cdr s)) (*A074679! s)) (else (*A089863! s))) s)
%Y Inverse: A123500. Row 258 of A089840. Variant of A074679.
%K nonn
%O 0,3
%A _Antti Karttunen_, Oct 11 2006