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-10 of 19 results. Next

A089848 Number of fixed points in range [A014137(n-1)..A014138(n-1)] of permutation A089851/A089853.

Original entry on oeis.org

1, 1, 2, 2, 5, 15, 42, 132, 431, 1430, 4862, 16801, 58786, 208012, 742914, 2674440, 9694845, 35357712, 129644790, 477638700, 1767263322, 6564120420, 24466267020, 91482564069, 343059613650, 1289904147324, 4861946402882, 18367353072152
Offset: 0

Views

Author

Antti Karttunen, Nov 29 2003

Keywords

Comments

The number of n-node binary trees fixed by the corresponding automorphism(s).

Links

Programs

Formula

a(0)=1, a(n) = A000108(n-1) if (n mod 3)=0 or 1 and a(n) = A000108(n-1)+A000108((n-2)/3) if (n mod 3)=2.

A089847 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A089851/A089853.

Original entry on oeis.org

1, 1, 2, 3, 8, 24, 72, 231, 764, 2574, 8840, 30796, 108528, 386308, 1386756, 5014575, 18249120, 66786738, 245642760, 907513530, 3366215688, 12531502620, 46805032560, 175341580596, 658674458208, 2480584898700, 9363748625972
Offset: 0

Views

Author

Antti Karttunen, Nov 29 2003

Keywords

Comments

The number of orbits to which the corresponding automorphism(s) partitions the set of A000108(n) binary trees with n internal nodes.

Links

Programs

Formula

a(n) = (1/3 * A000108(n)) + (2/3 * A089848(n))

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.

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

A089853 Permutation of natural numbers induced by Catalan automorphism *A089853 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Nov 29 2003

Keywords

Comments

This automorphism 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...B
....\./.............\./
.A...x....-->....C...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (c . (a . b)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this automorphism rotates car, cadr and cddr of an S-exp if its length > 1.
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

Links

Crossrefs

Inverse of A089851. a(n) = A072796(A089850(n)) = A057163(A089855(A057163(n))). Row 6 of A089840.
Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Extensions

Further comments and constructive implementation of Scheme-function (*A089853) added by Antti Karttunen, Jun 04 2011

A089857 Permutation of natural numbers induced by Catalan Automorphism *A089857 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Nov 29 2003

Keywords

Comments

.A...B...........C...A
..\./.............\./
...x...C....-->....x...B...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . a) . b) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism rotates caar, cdar and cdr of an S-exp, i.e., if car-side is not ().
See the Karttunen OEIS-Wiki link for a detailed explanation how to obtain a given integer sequence from this definition.

Links

Crossrefs

Row 11 of A089840. Inverse of A089855. a(n) = A074679(A069770(n)) = A069770(A089862(n)) = A057163(A089851(A057163(n))).
Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

Extensions

Further comments and constructive implementation of Scheme-function (*A089857) added by Antti Karttunen, Jun 04 2011

A089860 Permutation of natural numbers induced by Catalan automorphism *A089860 acting on the binary trees/parenthesizations encoded by A014486/A063171.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Nov 29 2003

Keywords

Comments

This automorphism 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.......C...A
......\./.........\./
...A...x...-->... .x...B...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
(a . (b . c)) --> ((c . a) . b) ___ (a . ()) --> (() . a)
See the Karttunen OEIS-Wiki link for a detailed explanation of how to obtain a given integer sequence from this definition.

Links

Crossrefs

Row 16 of A089840. Inverse of A089862. a(n) = A089855(A069770(n)) = A069770(A089851(n)) = A069770(A074680(A069770(n))) = A057163(A089862(A057163(n))).
Number of cycles: A001683 (probably, not checked). Number of fixed points: A019590. Max. cycle size & LCM of all cycle sizes: A089410 (in each range limited by A014137 and A014138).

Extensions

A graphical description and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A154121 Signature permutation of a Catalan bijection: row 3655 of A089840.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 06 2009

Keywords

Comments

This bijection of binary trees can be obtained by applying bijection *A074679 to the right hand side subtree and leaving the left hand side subtree intact:
....C...D.......B...C
.....\./.........\./
..B...x....-->....x...D.................B..().........()..B..
...\./.............\./...................\./....-->....\./...
A...x...........A...x.................A...x.........A...x....
.\./.............\./...................\./...........\./.....
..x...............x.....................x.............x......
.............................................................
Note that the first clause corresponds to generator B of Thompson's groups F, T and V, while *A074679's first clause corresponds to generator A and furthermore, *A089851 corresponds to generator C and *A072796 to generator pi_0 of Thompson's group V. (To be checked: can Thompson's V be embedded in A089840 by using these or some other suitably chosen generators?)
Comment to above: I think now that it is a misplaced hope to embed V in A089840. Instead, it is more probable that Thompson's V is isomorphic to the quotient group A089840/N, where N is a subgroup of A089840 which includes identity (*A001477) and any other bijection (e.g. *A154126) that fixes all large enough trees. For more details, see my "On the connection of A089840 with ..." page. - Antti Karttunen, Aug 23 2012

Links

Crossrefs

Inverse: A154122. a(n) = A069770(A089865(A069770(n))). Cf. A154123, A154126.

A130343 Row 4 of A122203.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 05 2007

Keywords

Comments

The signature-permutation of the Catalan automorphism which is derived from the fourth non-recursive Catalan automorphism *A089851 with recursion schema SPINE (see A122203 for the definition).

Links

Crossrefs

Inverse: A130344.

A130348 Row 4 of A122204.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 05 2007

Keywords

Comments

The signature-permutation of the Catalan automorphism which is derived from the fourth non-recursive Catalan automorphism *A089851 with recursion schema ENIPS (see A122204 for the definition).

Links

Crossrefs

Inverse: A130347.
Showing 1-10 of 19 results. Next

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

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