login
Signature-permutation of a Catalan automorphism, row 1654720 of A089840.
5

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

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

%T 63,64,57,61,54,45,46,55,48,49,50,56,60,53,44,47,52,43,40,31,32,41,34,

%U 35,36,51,42,39,30,33,37,28,23,24,38,29,25,26,27,170,171,174,175,176

%N Signature-permutation of a Catalan automorphism, row 1654720 of A089840.

%C This involution effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)

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

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

%C ...x...x....-->..x...x.......()..x..-->..x..()........x..()...-->..()..x..

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

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

%C Note that automorphism *A069770 = FORK(*A129604) = KROF(*A129604). See the definitions given in A122201 and A122202.

%H A. Karttunen, <a href="/A129604/b129604.txt">Table of n, a(n) for n = 0..2055</a>

%H A. Karttunen, <a href="/A089840/a089840p.txt">Prolog-program which illustrates the construction of this and similar nonrecursive Catalan automorphisms.</a>

%H <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>

%o (Constructive and destructive Scheme implementation of this automorphism. These act on S-expressions, i.e. list-structures:)

%o (define (*A129604 s) (cond ((pair? s) (cons (*A069770 (cdr s)) (*A069770 (car s)))) (else s)))

%o (define (*A129604! s) (cond ((pair? s) (*A069770! (car s)) (*A069770! (cdr s)) (*A069770! s))) s)

%Y a(n) = A069770(A089864(n)) = A089864(A069770(n)). The number of cycles and the number of fixed points in range [A014137(n-1)..A014138(n-1)] of this involution are given by the same sequences as is the case for example with A069770, A057163 and A122351, that is, A007595 and zero-interspersed A000108.

%K nonn

%O 0,3

%A _Antti Karttunen_, May 22 2007