

A122283


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


41



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, 10, 12, 8, 7, 5, 5, 4, 3, 2, 1, 0, 13, 17, 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 "DEEPEN". In this recursion scheme the given automorphism is first applied at the root of general tree, before the algorithm recurses down to all subtrees. I.e., this corresponds to the preorder (prefix) traversal of a Catalan structure, when it is interpreted as a general tree. The associated Schemeprocedures DEEPEN and !DEEPEN 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 A122284.
The recursion scheme FORK (described in A122201) is equivalent to a composition of recursion schemes SPINE (described in A122203) and DEEPEN, i.e., FORK(f) = DEEPEN(SPINE(f)) holds for all Catalan automorphisms f. These recursion schemes have welldefined inverses, that is, they are bijective mappings on the set of all Catalan automorphisms. Thus we can equivalently define that DEEPEN(f) = FORK(SPINE^{1}(f)). 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 A122283 form a (proper) subset of the rows of table A122201. E.g., row 1 of A122283 is row 21 of A122201, row 2 of A122283 is row 3613 of A122201, row 17 of A122283 is row 65352 of A122201, row 21 of A122283 is row 251 of A122201.  Antti Karttunen, May 25 2007


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 (DEEPEN foo) (letrec ((bar (lambda (s) (map bar (foo s))))) bar))
(define (!DEEPEN foo!) (letrec ((bar! (lambda (s) (foo! s) (foreach bar! s) s))) bar!))


CROSSREFS

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A122301, 2: A122300, 3: A122303, 4: A122305, 5: A122307, 6: A122309, 7: A122311, 8: A122313, 9: A122315, 10: A122317, 11: A122319, 12: A122321, 13: A122323, 14: A122325, 15: A122327, 16: A122329, 17: A122331, 18: A122333, 19: A122335, 20: A122337, 21: A122339. See also tables A089840, A122200, A122201A122204, A122285A122288, A122289A122290.
Sequence in context: A122284 A122203 A122287 * A122204 A122288 A122201
Adjacent sequences: A122280 A122281 A122282 * A122284 A122285 A122286


KEYWORD

nonn,tabl


AUTHOR

Antti Karttunen, Sep 01 2006


STATUS

approved



