

A122204


Signature permutations of ENIPStransformations of nonrecursive Catalan automorphisms in table A089840.


53



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, 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, 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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,4


COMMENTS

Row n is the signature permutation of the Catalan automorphism which is obtained from the nth nonrecursive automorphism in the table A089840 with the recursion scheme "ENIPS". In this recursion scheme the algorithm first recurses down to the righthand side branch of the binary tree, before the given automorphism is applied at its root. This corresponds to the foldright operation applied to the Catalan structure, interpreted e.g. as a parenthesization or a Lisplike list, where (lambda (x y) (f (cons x y))) is the binary function given to fold, with 'f' being the given automorphism. The associated Schemeprocedures 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.
Because of the "universal property of folds", the recursion scheme ENIPS has a welldefined 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 cdrbranch of a Sexpression (i.e. the right subtree in the context of binary trees). This implies that for any nonrecursive 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.


REFERENCES

A. Karttunen, paper in preparation, draft available by email.


LINKS

Table of n, a(n) for n=0..95.
Index entries for signaturepermutations of Catalan automorphisms


PROG

(MIT Scheme:) (define (ENIPS foo) (lambda (s) (foldright (lambda (x y) (foo (cons x y))) '() s)))
(define (!ENIPS foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (bar! (cdr s)) (foo! s))) s))) bar!))


CROSSREFS

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.
See also tables A089840, A122200, A122201A122203, A122283A122284, A122285A122288, A122289A122290.
Sequence in context: A122203 A122287 A122283 * A122288 A122201 A122286
Adjacent sequences: A122201 A122202 A122203 * A122205 A122206 A122207


KEYWORD

nonn,tabl


AUTHOR

Antti Karttunen, Sep 01 2006, Jun 06 2007


STATUS

approved



