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-5 of 5 results.

A122204 Signature permutations of ENIPS-transformations of non-recursive Catalan automorphisms in table A089840.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 01 2006, Jun 06 2007

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 "ENIPS". In this recursion scheme the algorithm first recurses down to the right-hand side branch of the binary tree, before the given automorphism is applied at its root. This corresponds to the fold-right operation applied to the Catalan structure, interpreted e.g. as a parenthesization or a Lisp-like list, where (lambda (x y) (f (cons x y))) is the binary function given to fold, with 'f' being the given automorphism. The associated Scheme-procedures ENIPS and !ENIPS 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 A122203.
Because of the "universal property of folds", the recursion scheme ENIPS has a well-defined inverse, that is, it acts as a bijective mapping on the set of all Catalan automorphisms. 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 A089840 form a (proper) subset of the rows of this table.

References

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

Links

Crossrefs

Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069768, 2: A057510, 3: A130342, 4: A130348, 5: A130346, 6: A130344, 7: A122282, 8: A082340, 9: A130354, 10: A130352, 11: A130350, 12: A057502, 13: A130364, 14: A130366, 15: A069770, 16: A130368, 17: A074686, 18: A130356, 19: A130358, 20: A130362, 21: A130360. Other rows: row 169: A089859, row 253: A123718, row 3608: A129608, row 3613: A072796, row 65167: A074679, row 79361: A123716.
See also tables A089840, A122200, A122201-A122203, A122283-A122284, A122285-A122288, A122289-A122290.

A072796 Self-inverse permutation of natural numbers induced by the Catalan bijection swapping the two leftmost subtrees in the general tree context of the parenthesizations encoded by A014486. See illustrations in the comments.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 14, 16, 19, 11, 15, 12, 17, 18, 13, 20, 21, 22, 23, 24, 25, 26, 27, 37, 38, 42, 44, 47, 51, 53, 56, 60, 28, 29, 39, 43, 52, 30, 40, 31, 45, 46, 32, 48, 49, 50, 33, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71
Offset: 0

Views

Author

Antti Karttunen, Jun 12 2002

Keywords

Comments

This bijection effects the following transformation on the unlabeled rooted plane general trees (letters A, B, C, etc. refer to arbitrary subtrees located on those vertices):
A A A B B A A B C B A C
| --> | \ / --> \ / \ | / --> \ | /
| | \./ \./ \|/ \|/ etc.
I.e., it keeps "planted" (root degree = 1) trees intact, and swaps the two leftmost toplevel subtrees of the general trees that have a root degree > 1.
On the level of underlying binary trees that general trees map to (see, e.g., 1967 paper by N. G. De Bruijn and B. J. M. Morselt, or consider lists vs. dotted pairs in Lisp programming language), this bijection effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node).
B C A C
\ / \ /
A x --> B x A () A ()
\ / \ / \ / --> \ /
x x x x
(a . (b . c)) -> (b . (a . c)) (a . ()) ---> (a . ())
Note that the first clause corresponds to what is called "generator pi_0" in Thompson's group V. (See also A074679, A089851 and A154121 for other related generators.)
Look at the example section to see how this will produce the given sequence of integers.
Applying this permutation recursively down the right hand side branch of the binary trees (or equivalently, along the topmost level of the general trees) produces permutations A057509 and A057510 (that occur at the same index 2 in tables A122203 and A122204) that effect "shallow rotation" on general trees and parenthesizations. Applying it recursively down the both branches of binary trees (as in pre- or postorder traversal) produces A057511 and A057512 (that occur at the same index 2 in tables A122201 and A122201) that effect "deep rotation" on general trees and parenthesizations.
For this permutation, A127301(a(n)) = A127301(n) for all n, which in turn implies A129593(a(n)) = A129593(n) for all n, likewise for all such recursively generated bijections as A057509 - A057512. Compare also to A072797.

Examples

			To obtain the signature permutation, we apply these transformations to the binary trees as encoded and ordered by A014486 and for each n, a(n) will be the position of the tree to which the n-th tree is transformed to, as follows:
.
                   one tree of one internal
  empty tree         (non-leaf) node
      x                      \/
n=    0                      1
a(n)= 0                      1               (both are always fixed)
.
the next 7 trees, with 2-3 internal nodes, in range [A014137(1), A014137(2+1)-1] = [2,8] are:
.
                          \/     \/                 \/     \/
       \/     \/         \/       \/     \/ \/     \/       \/
      \/       \/       \/       \/       \_/       \/       \/
n=     2        3        4        5        6        7        8
.
and the new shapes after swapping the two subtrees in positions marked "A" and "B" in the diagram given in the comments are:
.
                          \/               \/       \/     \/
       \/     \/         \/     \/ \/       \/     \/       \/
      \/       \/       \/       \_/       \/       \/       \/
a(n)=  2        3        4        6        5        7        5
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 6, 5, 7, 8.

Links

Crossrefs

Row 2 of A089840. Row 3613 of A122203 and row 3617 of A122204.
Fixed point counts and cycle counts are given in A073190 and A073191.
Cf. A014486, A072797, A057509, A057510, A057511, A057512, A127301, A129593, A129608.

Extensions

Comment section edited and Examples added by Antti Karttunen, Jan 26 2024

A122203 Signature permutations of SPINE-transformations of non-recursive Catalan automorphisms in table A089840.

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, 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
Offset: 0

Views

Author

Antti Karttunen, Sep 01 2006, Jun 06 2007

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 "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 right-hand side branch. The associated Scheme-procedures 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 well-defined 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 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 A089840 form a (proper) subset of the rows of this table.

References

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

Links

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, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290.

Programs

  • 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!))

A130339 Signature permutation of a Catalan automorphism: swap the two rightmost subtrees of general trees, if the root degree (A057515(n)) is even.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 11, 16, 19, 14, 15, 12, 17, 18, 13, 20, 21, 22, 23, 25, 24, 26, 27, 28, 29, 30, 44, 47, 33, 53, 56, 60, 37, 38, 39, 43, 52, 42, 40, 31, 45, 46, 32, 48, 49, 50, 51, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 66, 67, 72, 75, 70, 71
Offset: 0

Views

Author

Antti Karttunen, Jun 05 2007

Keywords

Comments

This self-inverse automorphism is obtained as either SPINE(*A129608) or ENIPS(*A129608). See the definitions given in A122203 and A122204.

Links

Crossrefs

Cf. a(n) = A057508(A130340(A057508(n))) = A057164(A130340(A057164(n))). Row 3608 of A122285 and A122286. a(n) = A129608(n), if A057515(n) mod 2 = 0, otherwise a(n)=n.

A129607 Signature-permutation of a Catalan automorphism: swap the left and right subtree of degree 2 general trees.

Original entry on oeis.org

0, 1, 2, 3, 4, 6, 5, 7, 8, 9, 10, 11, 16, 19, 14, 15, 12, 17, 18, 13, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 44, 47, 33, 53, 56, 60, 37, 38, 39, 43, 52, 42, 40, 31, 45, 46, 32, 48, 49, 50, 51, 41, 34, 54, 55, 35, 57, 58, 59, 36, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71
Offset: 0

Views

Author

Antti Karttunen, May 22 2007

Keywords

Comments

Otherwise like automorphism *A072796, except that this involution exchanges the two leftmost subtrees of a general tree ONLY when the degree of the tree is two. Automorphism *A129608 = SPINE(*A129607) = ENIPS(*A129607). See the definitions given in A122203 and A122204.

Links

Crossrefs

Row 3608 of A089840.
Showing 1-5 of 5 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.