

A122203


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


46



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, 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, 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
(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 "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 righthand side branch. The associated Schemeprocedures 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.
The recursion scheme SPINE has a welldefined 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 cdrbranch of a Sexpression. This implies that for any nonrecursive 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.


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

(Scheme:) (define (SPINE foo) (letrec ((bar (lambda (s) (let ((t (foo s))) (if (pair? t) (cons (car t) (bar (cdr t))) t))))) bar))
(define (!SPINE foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! s) (bar! (cdr s)))) s))) bar!))


CROSSREFS

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.
See also tables A089840, A122200, A122201A122204, A122283A122284, A122285A122288, A122289A122290.
Sequence in context: A122289 A122290 A122284 * A122287 A122283 A122204
Adjacent sequences: A122200 A122201 A122202 * A122204 A122205 A122206


KEYWORD

nonn,tabl


AUTHOR

Antti Karttunen, Sep 01 2006, Jun 06 2007


STATUS

approved



