login
Signature permutations of ENIPS-transformations of non-recursive Catalan automorphisms in table A089840.
54

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

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

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

%U 21,9,8,7,4,4,4,3,2,1,0,12,20,14,13,8,7,5,5,4,3,2,1,0,13,17,10,12,13

%N Signature permutations of ENIPS-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 "ENIPS". In this recursion scheme the algorithm first recurses down to the right-hand side branch of the binary tree, before the given automorphism is applied at its root. This corresponds to the fold-right operation applied to the Catalan structure, interpreted e.g. as a parenthesization or a Lisp-like list, where (lambda (x y) (f (cons x y))) is the binary function given to fold, with 'f' being the given automorphism. The associated Scheme-procedures ENIPS and !ENIPS 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 A122203.

%C Because of the "universal property of folds", the recursion scheme ENIPS has a well-defined inverse, that is, it acts as a bijective mapping on the set of all Catalan automorphisms. Specifically, if g = ENIPS(f), then (f s) = (g (cons (car s) (g^{-1} (cdr s)))), that is, to obtain an automorphism f which gives g when subjected to recursion scheme ENIPS, we compose g with its own inverse applied to the cdr-branch of a S-expression (i.e. the right subtree in the context of binary trees). This implies that for any non-recursive automorphism f in the table A089840, ENIPS^{-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 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 (MIT Scheme:) (define (ENIPS foo) (lambda (s) (fold-right (lambda (x y) (foo (cons x y))) '() s)))

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

%Y Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069768, 2: A057510, 3: A130342, 4: A130348, 5: A130346, 6: A130344, 7: A122282, 8: A082340, 9: A130354, 10: A130352, 11: A130350, 12: A057502, 13: A130364, 14: A130366, 15: A069770, 16: A130368, 17: A074686, 18: A130356, 19: A130358, 20: A130362, 21: A130360. Other rows: row 169: A089859, row 253: A123718, row 3608: A129608, row 3613: A072796, row 65167: A074679, row 79361: A123716.

%Y See also tables A089840, A122200, A122201-A122203, A122283-A122284, A122285-A122288, A122289-A122290.

%K nonn,tabl

%O 0,4

%A _Antti Karttunen_, Sep 01 2006, Jun 06 2007