login
Signature permutations of RIBS-transformations of non-recursive Catalan automorphisms in table A089840.
20

%I #8 Mar 31 2012 13:21:11

%S 0,1,0,2,1,0,3,2,1,0,4,3,2,1,0,5,4,3,2,1,0,6,5,4,3,2,1,0,7,6,5,4,3,2,

%T 1,0,8,8,6,5,4,3,2,1,0,9,7,7,6,5,4,3,2,1,0,10,9,8,7,6,5,4,3,2,1,0,11,

%U 10,9,8,7,6,5,4,3,2,1,0,12,11,10,9,8,7,6,5,4,3,2,1,0,13,13,11,10,9,8

%N Signature permutations of RIBS-transformations of non-recursive Catalan automorphisms in table A089840.

%C Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th nonrecursive automorphism in the table A089840 with the recursion scheme "RIBS".

%C In this recursion scheme the given automorphism is applied to all (toplevel) subtrees of the Catalan structure, when it is interpreted as a general tree. Permutations in this table form a countable group, which is isomorphic with the group in A089840. (The RIBS transformation gives the group isomorphism.)

%C Furthermore, row n of this table is also found as the row A123694(n) in tables A122203 and A122204. If the count of fixed points of the automorphism A089840[n] is given by sequence f, then the count of fixed points of the automorphism A089840[A123694(n)] is given by CONV(f,A000108) (where CONV stands for convolution) and the count of fixed points of the automorphism A122200[n] by INVERT(RIGHT(f)).

%C The associated Scheme-procedures RIBS and !RIBS can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism.

%C Comment from Antti Karttunen, May 11 2008: This sequence agrees with A025581 in its initial terms, but then diverges from it.

%D A. Karttunen, paper in preparation, draft available by e-mail.

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

%o (Scheme) (define (RIBS foo) (lambda (s) (map foo s)))

%o (define (!RIBS foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! (car s)) (bar! (cdr s)))) s))) bar!))

%Y Row 0 (identity permutation): A001477, row 1: A122282. See also tables A089840, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.

%K nonn,tabl

%O 0,4

%A _Antti Karttunen_, Sep 01 2006