login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A122284 Signature permutations of NEPEED-transformations of non-recursive Catalan automorphisms in table A089840. 38
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, 10, 12, 8, 7, 5, 5, 4, 3, 2, 1, 0, 13, 22, 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 n-th nonrecursive automorphism in the table A089840 with the recursion scheme "NEPEED". In this recursion scheme the algorithm first recurses down to all subtrees, before the given automorphism is applied at the root of general tree. I.e., this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a general tree. The associated Scheme-procedures NEPEED and !NEPEED 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 A122283.

The recursion scheme KROF (described in A122202) is equivalent to a composition of recursion schemes ENIPS (described in A122204) and NEPEED, i.e., KROF(f) = NEPEED(ENIPS(f)) holds for all Catalan automorphisms f. Because of the "universal property of folds", these recursion schemes have well-defined inverses, that is, they are bijective mappings on the set of all Catalan automorphisms. Thus we can equivalently define that NEPEED(f) = KROF(ENIPS^{-1}(f)). 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 A122284 form a (proper) subset of the rows of table A122202. E.g., row 1 of A122284 is row 15 of A122202, row 2 of A122284 is row 3617 of A122202, row 12 of A122284 is row 65167 of A122202, row 15 of A122284 is row 169 of A122202. - Antti Karttunen, May 25 2007

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 well-defined 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 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 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 e-mail.

LINKS

Table of n, a(n) for n=0..95.

Index entries for signature-permutations of Catalan automorphisms

PROG

(Scheme:) (define (NEPEED foo) (letrec ((bar (lambda (s) (foo (map bar s))))) bar))

(define (!NEPEED foo!) (letrec ((bar! (lambda (s) (for-each bar! s) (foo! s) s))) bar!))

CROSSREFS

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A122302, 2: A122300, 3: A122304, 4: A122310, 5: A122308, 6: A122306, 7: A122312, 8: A122314, 9: A122320, 10: A122318, 11: A122316, 12: A122332, 13: A122334, 14: A122336, 15: A122340, 16: A122338, 17: A122322, 18: A122324, 19: A122326, 20: A122330, 21: A122328. See also tables A089840, A122200, A122201-A122204, A122285-A122288, A122289-A122290.

Sequence in context: A130401 A122289 A122290 * A122203 A122287 A122283

Adjacent sequences:  A122281 A122282 A122283 * A122285 A122286 A122287

KEYWORD

nonn,tabl

AUTHOR

Antti Karttunen, Sep 01 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 26 23:02 EDT 2019. Contains 321565 sequences. (Running on oeis4.)