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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A122202 Signature permutations of KROF-transformations of non-recursive Catalan automorphisms in table A089840. 35
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, 5, 5, 4, 5, 3, 2, 1, 0, 9, 4, 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, 18, 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 n-th nonrecursive automorphism in the table A089840 with the recursion scheme "KROF". In this recursion scheme the algorithm first recurses down to the both branches, before the given automorphism is applied at the root of binary tree. I.e., this corresponds to the post-order (postfix) traversal of a Catalan structure, when it is interpreted as a binary tree. The associated Scheme-procedures KROF and !KROF 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 A122201.

The recursion scheme KROF is equivalent to a composition of recursion schemes ENIPS (described in A122204) and NEPEED (described in A122284), 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. Specifically, if g = KROF(f), then (f s) = (g (cons (g^{-1} (car s)) (g^{-1} (cdr s)))), that is, to obtain an automorphism f which gives g when subjected to recursion scheme KROF, we compose g with its own inverse applied to the car- and cdr-branches of a S-expression (i.e., the left and right subtrees in the context of binary trees). This implies that for any nonrecursive automorphism f of the table A089840, KROF^{-1}(f) is also in A089840, which in turn implies that all rows of table A089840 can be found also in table A122202 (e.g., row 1 of A089840 (A069770) occurs here as row 1654720) and furthermore, the table A122290 contains the rows of both tables, A122202 and A089840 as its subsets. Similar notes apply to recursion scheme FORK described in 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

(MIT Scheme:) (define (KROF foo) (letrec ((bar (lambda (s) (fold-right (lambda (x y) (foo (cons (bar x) y))) '() s)))) bar))

(define (!KROF foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (bar! (car s)) (bar! (cdr s)) (foo! s))) s))) bar!))

CROSSREFS

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A057163, 2: A057512, 3: A122342, 4: A122348, 5: A122346, 6: A122344, 7: A122350, 8: A082326, 9: A122294, 10: A122292, 11: A082359, 12: A074683, 13: A122358, 14: A122360, 15: A122302, 16: A122362, 17: A074682, 18: A122296, 19: A122298, 20: A122356, 21: A122354. Other rows: row 4069: A082355, row 65518: A082357, row 79361: A123494.

See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.

Row 1654720: A069770.

Sequence in context: A122288 A122201 A122286 * A122285 A100224 A208671

Adjacent sequences:  A122199 A122200 A122201 * A122203 A122204 A122205

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 24 19:48 EDT 2019. Contains 321448 sequences. (Running on oeis4.)