cp's OEIS Frontend

A122203 Signature permutations of SPINE-transformations of non-recursive Catalan automorphisms in table A089840.

%I A122203 #12 Jul 24 2025 20:49:15
%S A122203 0,1,0,2,1,0,3,3,1,0,4,2,2,1,0,5,7,3,2,1,0,6,8,4,3,2,1,0,7,6,6,5,3,2,
%T A122203 1,0,8,5,5,4,5,3,2,1,0,9,4,7,6,6,6,3,2,1,0,10,17,8,7,4,5,6,3,2,1,0,11,
%U A122203 18,9,8,7,4,4,4,3,2,1,0,12,20,11,12,8,7,5,5,4,3,2,1,0,13,21,14,13,12
%N A122203 Signature permutations of SPINE-transformations of non-recursive Catalan automorphisms in table A089840.
%C A122203 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 "SPINE". In this recursion scheme the given automorphism is first applied at the root of binary tree, before the algorithm recurses down to the new right-hand side branch. The associated Scheme-procedures SPINE and !SPINE can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism. Each row occurs only once in this table. Inverses of these permutations can be found in table A122204.
%C A122203 The recursion scheme SPINE has a well-defined inverse, that is, it acts as a bijective mapping on the set of all Catalan automorphisms. Specifically, if g = SPINE(f), then (f s) = (cond ((pair? s) (let ((t (g s))) (cons (car t) (g^{-1} (cdr t))))) (else s)) that is, to obtain an automorphism f which gives g when subjected to recursion scheme SPINE, we compose g with its own inverse applied to the cdr-branch of a S-expression. This implies that for any non-recursive automorphism f in the table A089840, SPINE^{-1}(f) is also in A089840, which in turn implies that the rows of table A089840 form a (proper) subset of the rows of this table.
%D A122203 A. Karttunen, paper in preparation, draft available by e-mail.
%H A122203 <a href="/index/Per#IntegerPermutationCatAuto">Index entries for signature-permutations of Catalan automorphisms</a>
%o A122203 (Scheme) (define (SPINE foo) (letrec ((bar (lambda (s) (let ((t (foo s))) (if (pair? t) (cons (car t) (bar (cdr t))) t))))) bar))
%o A122203 (define (!SPINE foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! s) (bar! (cdr s)))) s))) bar!))
%Y A122203 Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069767, 2: A057509, 3: A130341, 4: A130343, 5: A130345, 6: A130347, 7: A122282, 8: A082339, 9: A130349, 10: A130351, 11: A130353, 12: A074685, 13: A130355, 14: A130357, 15: A130359, 16: A130361, 17: A057501, 18: A130363, 19: A130365, 20: A130367, 21: A069770. Other rows: row 251: A089863, row 253: A123717, row 3608: A129608, row 3613: A072796, row 65352: A074680, row 79361: A123715.
%Y A122203 See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.
%K A122203 nonn,tabl
%O A122203 0,4
%A A122203 _Antti Karttunen_, Sep 01 2006, Jun 06 2007