cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-3 of 3 results.

A089840 Signature permutations of non-recursive Catalan automorphisms (i.e., bijections of finite plane binary trees, with no unlimited recursion down to indefinite distances from the root), sorted according to the minimum number of opening nodes needed in their defining clauses.

Original entry on oeis.org

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, 4, 5, 4, 5, 3, 2, 1, 0, 9, 5, 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, 21, 14, 13, 12, 8, 7, 6
Offset: 0

Views

Author

Antti Karttunen, Dec 05 2003; last revised Jan 06 2009

Keywords

Comments

Each row is a permutation of natural numbers and occurs only once. The table is closed with regards to the composition of its rows (see A089839) and it contains the inverse of each (their positions are shown in A089843). The permutations in table form an enumerable subgroup of the group of all size-preserving "Catalan bijections" (bijections among finite unlabeled rooted plane binary trees). The order of each element is shown at A089842.

References

  • A. Karttunen, paper in preparation, draft available by e-mail.

Links

Crossrefs

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069770, 2: A072796, 3: A089850, 4: A089851, 5: A089852, 6: A089853, 7: A089854, 8: A072797, 9: A089855, 10: A089856, 11: A089857, 12: A074679, 13: A089858, 14: A073269, 15: A089859, 16: A089860, 17: A074680, 18: A089861, 19: A073270, 20: A089862, 21: A089863.
Other rows: row 83: A154125, row 169: A129611, row 183: A154126, row 251: A129612, row 253: A123503, row 258: A123499, row 264: A123500, row 3608: A129607, row 3613: A129605, row 3617: A129606, row 3655: A154121, row 3656: A154123,row 3702: A082354, row 3747: A154122, row 3748: A154124, row 3886: A082353, row 4069: A082351, row 4207: A089865, row 4253: A082352, row 4299: A089866, row 65167: A129609, row 65352: A129610, row 65518: A123495, row 65796: A123496, row 79361: A123492, row 1653002: A123695, row 1653063: A123696, row 1654023: A073281, row 1654249: A123498, row 1654694: A089864, row 1654720: A129604,row 1655089: A123497, row 1783367: A123713, row 1786785: A123714.
Tables A122200, A122201, A122202, A122203, A122204, A122283, A122284, A122285, A122286, A122287, A122288, A122289, A122290, A130400-A130403 give various "recursive derivations" of these non-recursive automorphisms. See also A089831, A073200.
Index sequences to this table, giving various subgroups or other important constructions: A153826, A153827, A153829, A153830, A123694, A153834, A153832, A153833.

A122200 Signature permutations of RIBS-transformations of non-recursive Catalan automorphisms in table A089840.

Original entry on oeis.org

0, 1, 0, 2, 1, 0, 3, 2, 1, 0, 4, 3, 2, 1, 0, 5, 4, 3, 2, 1, 0, 6, 5, 4, 3, 2, 1, 0, 7, 6, 5, 4, 3, 2, 1, 0, 8, 8, 6, 5, 4, 3, 2, 1, 0, 9, 7, 7, 6, 5, 4, 3, 2, 1, 0, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, 13, 13, 11, 10, 9, 8
Offset: 0

Views

Author

Antti Karttunen, Sep 01 2006

Keywords

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 "RIBS".
In this recursion scheme the given automorphism is applied to all (toplevel) subtrees of the Catalan structure, when it is interpreted as a general tree. Permutations in this table form a countable group, which is isomorphic with the group in A089840. (The RIBS transformation gives the group isomorphism.)
Furthermore, row n of this table is also found as the row A123694(n) in tables A122203 and A122204. If the count of fixed points of the automorphism A089840[n] is given by sequence f, then the count of fixed points of the automorphism A089840[A123694(n)] is given by CONV(f,A000108) (where CONV stands for convolution) and the count of fixed points of the automorphism A122200[n] by INVERT(RIGHT(f)).
The associated Scheme-procedures RIBS and !RIBS can be used to obtain such a transformed automorphism from any constructively or destructively implemented automorphism.
This sequence agrees with A025581 in its initial terms, but then diverges from it. - Antti Karttunen, May 11 2008

References

  • Antti Karttunen, paper in preparation, draft available by e-mail.

Links

Crossrefs

Row 0 (identity permutation): A001477, row 1: A122282. See also tables A089840, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.

Programs

  • Scheme
    (define (RIBS foo) (lambda (s) (map foo s)))
(define (!RIBS foo!) (letrec ((bar! (lambda (s) (cond ((pair? s) (foo! (car s)) (bar! (cdr s)))) s))) bar!))

A153834 Index sequence to A089840: position of A089840(n) when applied to the right hand side subtree.

Original entry on oeis.org

0, 3, 23, 27, 29, 33, 35, 46, 50, 52, 56, 58, 3655, 3659, 3667, 3677, 3681, 3747, 3751, 3759, 3763, 3771, 277, 281, 283, 287, 289, 299, 301, 305, 307, 311, 313, 323, 325, 329, 331, 335, 337, 347, 349, 353, 355, 359, 361, 396, 400, 402, 406, 408, 418, 420
Offset: 0

Views

Author

Antti Karttunen, Jan 07 2009

Keywords

Comments

The comments at A123694 concerning counts of fixed points apply also here.

Examples

			When A089840(1) = A069770 (swap binary tree sides) is applied to the right subtree of a binary tree, we get A089850 = A089840(3), thus a(1)=3. When A089840(12) = A074679 is applied to the right subtree of a binary tree, we get A154121 = A089840(3655), thus a(12)=3655.

Links

Crossrefs

a(n) < A123694(n) for all n > 0. Used to construct A153832 and A153833.
Showing 1-3 of 3 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.