login
An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism which swaps the sides of a binary tree if the left subtree of either the left or right hand side toplevel subtree is not empty and otherwise keeps the binary tree intact.
8

%I #6 Mar 31 2012 13:21:12

%S 0,1,2,3,4,8,6,7,5,9,10,20,21,22,14,19,16,17,18,15,11,12,13,23,24,25,

%T 26,27,54,55,57,58,59,61,62,63,64,37,38,53,56,60,42,51,44,45,46,47,48,

%U 49,50,43,52,39,28,29,40,30,31,32,41,33,34,35,36,65,66,67,68,69,70,71

%N An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism which swaps the sides of a binary tree if the left subtree of either the left or right hand side toplevel subtree is not empty and otherwise keeps the binary tree intact.

%C This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C and D refer to arbitrary subtrees located on those nodes.)

%C .....B...C.....B...C...........A...B.............A...B...

%C ......\./.......\./.............\./...............\./....

%C .......x...D.....x...D...........x...C.............x...C.

%C ........\./.......\./.............\./...............\./..

%C .....A...x...-->...x...A...........x...D...-->...D...x...

%C ......\./...........\./.............\./...........\./....

%C .......x.............x...............x.............x.....

%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 (*A123492! s) (cond ((null? s) s) ((and (pair? (cdr s)) (pair? (cadr s))) (*A069770! s)) ((and (pair? (car s)) (pair? (caar s))) (*A069770! s))) s)

%Y Row 79361 of A089840. Used to construct A123493, A123494, A123715 and A123716. Cf. A069770.

%K nonn

%O 0,3

%A _Antti Karttunen_, Oct 11 2006