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”).

Signature permutation of a Catalan automorphism: apply *A074679 to the root and recurse down the cdr-spine (the right-hand side edge of a binary tree) as long as the binary tree rotation is possible and if the top-level length (A057515(n)) is odd, then apply *A069770 to the last branch-point.
10

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

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

%T 37,38,43,42,44,45,46,47,48,49,50,52,51,53,54,55,56,57,58,23,24,59,25,

%U 26,27,60,61,62,28,29,63,30,31,32,64,33,34,35,36,113,112,114,115,116

%N Signature permutation of a Catalan automorphism: apply *A074679 to the root and recurse down the cdr-spine (the right-hand side edge of a binary tree) as long as the binary tree rotation is possible and if the top-level length (A057515(n)) is odd, then apply *A069770 to the last branch-point.

%C This automorphism converts lists of even length (1 2 3 4 ... 2n-1 2n) to the form ((1 . 2) (3 . 4) ... (2n-1 . 2n)) and when applied to lists of odd length, like (1 2 3 4 5), i.e. (1 . (2 . (3 . (4 . (5 . ()))))), converts them as ((1 . 2) . ((3 . 4) . (() . 5))).

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

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

%o (Destructive Scheme implementation of this automorphism, which acts on S-expressions, i.e. list-structures:)

%o (define (*A130369! s) (cond ((not (pair? s))) ((not (pair? (cdr s))) (*A069770! s)) (else (*A074679! s) (*A130369! (cdr s)))) s)

%Y Inverse: A130370. a(n) = A074685(A130372(n)) = A130376(A074685(n)). The number of cycles, number of fixed points, maximum cycle sizes and LCM's of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of this permutation are given by A130377, LEFT(A019590), A130378 and A130379.

%K nonn

%O 0,3

%A _Antti Karttunen_, Jun 05 2007