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 17 results. Next

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.

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

Original entry on oeis.org

0, 1, 3, 2, 8, 7, 6, 4, 5, 21, 22, 20, 17, 18, 19, 16, 14, 9, 10, 15, 11, 12, 13, 58, 59, 62, 63, 64, 57, 61, 54, 45, 46, 55, 48, 49, 50, 56, 60, 53, 44, 47, 51, 42, 37, 23, 24, 38, 25, 26, 27, 52, 43, 39, 28, 29, 40, 30, 31, 32, 41, 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...B
......\./.........\./
...A...x...-->... .x...A...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
(a . (b . c)) --> ((c . b) . a) ___ (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 15 of A089840. Inverse of A089863. a(n) = A089854(A069770(n)) = A069770(A089850(n)). A089864 is the "square" of this permutation.
Number of cycles: A089407. Max. cycle size & LCM of all cycle sizes: A040002 (in each range limited by A014137 and A014138).

Extensions

A graphical description and constructive implementation of Scheme-function (*A089859) added by Antti Karttunen, Jun 04 2011

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

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 6, 5, 4, 17, 18, 20, 21, 22, 16, 19, 15, 12, 13, 14, 11, 9, 10, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 44, 47, 53, 56, 60, 43, 52, 40, 31, 32, 41, 34, 35, 36, 42, 51, 39, 30, 33, 37, 28, 23, 24, 38, 29, 25, 26, 27, 129, 130, 132, 133, 134
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).
.A...B...............B...A
..\./.................\./
...x...C...-->.....C...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (c . (b . a)) __ (() . 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 21 of A089840. Inverse of A089859. a(n) = A089850(A069770(n)) = A069770(A089854(n)). A089864 is the "square" of this permutation.
Number of cycles: A089407. Max. cycle size & LCM of all cycle sizes: A040002 (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

A127302 Matula-Goebel signatures for plane binary trees encoded by A014486.

Original entry on oeis.org

1, 4, 14, 14, 86, 86, 49, 86, 86, 886, 886, 454, 886, 886, 301, 301, 301, 886, 886, 301, 454, 886, 886, 13766, 13766, 6418, 13766, 13766, 3986, 3986, 3986, 13766, 13766, 3986, 6418, 13766, 13766, 3101, 3101, 1589, 3101, 3101, 1849, 1849, 3101, 13766
Offset: 0

Views

Author

Antti Karttunen, Jan 16 2007

Keywords

Comments

This sequence maps A000108(n) oriented (plane) rooted binary trees encoded in range [A014137(n-1)..A014138(n-1)] of A014486 to A001190(n+1) non-oriented rooted binary trees, encoded by their Matula-Goebel numbers (when viewed as a subset of non-oriented rooted general trees). See also the comments at A127301.
If the signature-permutation of a Catalan automorphism SP satisfies the condition A127302(SP(n)) = A127302(n) for all n, then it preserves the non-oriented form of a binary tree. Examples of such automorphisms include A069770, A057163, A122351, A069767/A069768, A073286-A073289, A089854, A089859/A089863, A089864, A122282, A123492-A123494, A123715/A123716, A127377-A127380, A127387 and A127388.
A153835 divides natural numbers to same equivalence classes, i.e. a(i) = a(j) <=> A153835(i) = A153835(j) - Antti Karttunen, Jan 03 2013

Examples

			A001190(n+1) distinct values occur each range [A014137(n-1)..A014138(n-1)]. As an example, terms A014486(4..8) encode the following five plane binary trees:
........\/.....\/.................\/.....\/...
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
n=.....4........5........6........7........8..
The trees in positions 4, 5, 7 and 8 all produce Matula-Goebel number A000040(1)*A000040(A000040(1)*A000040(A000040(1)*A000040(1))) = 2*A000040(2*A000040(2*2)) = 2*A000040(14) = 2*43 = 86, as they are just different planar representations of the one and same non-oriented tree. The tree in position 6 produces Matula-Goebel number A000040(A000040(1)*A000040(1)) * A000040(A000040(1)*A000040(1)) = A000040(2*2) * A000040(2*2) = 7*7 = 49. Thus a(4..8) = 86,86,49,86,86.

Links

Crossrefs

Cf A127301, A153835, A153829.

Formula

a(n) = A127301(A057123(n)).
Can be also computed directly as a fold, see the Scheme-program. - Antti Karttunen, Jan 03 2013

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

Original entry on oeis.org

0, 1, 2, 3, 5, 4, 6, 7, 8, 12, 13, 11, 9, 10, 15, 14, 16, 17, 18, 19, 20, 21, 22, 31, 32, 34, 35, 36, 30, 33, 28, 23, 24, 29, 25, 26, 27, 40, 41, 39, 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, 87, 88, 90, 91, 92, 96, 97, 99
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...B
....\./.............\./
.A...x....-->....A...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (a . (c . b)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this automorphism swaps cadr and cddr of an S-exp if its length > 1.
Look at the example in A069770 to see how this will produce the given sequence of integers.

Links

Crossrefs

a(n) = A069770(A089859(n)) = A089863(A069770(n)) = A057163(A089854(A057163(n))). Row 3 of A089840. Row 3771 of A122203 and row 3677 of A122204.
Number of cycles: A073191. Number of fixed points: A073190. Max. cycle size & LCM of all cycle sizes: A046698 (in each range limited by A014137 and A014138).

Extensions

The new mail-address, a graphical explanation and constructive implementation of Scheme-function (*A089850) added by Antti Karttunen, Jun 04 2011

A122282 Row 1 of A122200, row 7 of A122203 and A122204.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Sep 01 2006

Keywords

Comments

An involution of nonnegative integers.
The signature-permutation of the automorphism which is derived from the first non-recursive automorphism *A069770 with the recursion schema RIBS (see A122200), or alternatively, derived from the seventh non-recursive automorphism *A089854 with recursion scheme SPINE or ENIPS (see A122203, A122204 for their definitions).

Links

Crossrefs

The number of fixed points in range [A014137(n-1)..A014138(n-1)] of this permutation is given by INVERT transform of "aerated" Catalan numbers [1, 1, 0, 1, 0, 2, 0, 5, 0, 14, 0, 42, ...].

A123503 An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism, row 253 of table A089840.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Oct 11 2006

Keywords

Comments

This automorphism either swaps (if A057515(n) > 1) the first two toplevel elements (of a general plane tree, like *A072796 does) and otherwise (if n > 1, A057515(n)=1) swaps the sides of the left hand side subtree of the S-expression (when viewed as a binary tree, like *A089854 does). This is illustrated below, where letters A, B and C refer to arbitrary subtrees located on those nodes and () stands for an implied terminal node.
...B...C.............A...C............A...B...........B...A
....\./...............\./..............\./.............\./
.A...x.....-->.....B...x................x..()....-->....x..()
..\./...............\./..................\./.............\./
...x....(A072796)....x....................x...(A089854)...x
(a . (b . c)) --> (b . (a . c)) / ((a . b) . ()) --> ((b . a) . ())
This is the first multiclause automorphism in table A089840 which cannot be represented as a composition of two smaller nonrecursive automorphisms, the property which is also shared by *A123499 and *A123500.

Links

Crossrefs

Row 253 of A089840. Used to construct A123717 and A123718.

A154453 Signature permutation of a Catalan bijection induced by generator "a" of the leftward recursing instance of Basilica group wreath recursion: a = (b,1), b = s(a,1).

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 17 2009

Keywords

Comments

This automorphism of rooted plane binary trees switches the two descendant trees for every other vertex as it returns back toward the root, after descending down to the leftmost tip of the tree along the 000... ray, so that the last vertex whose descendants are swapped, is the left-hand side child of the root and the root itself is fixed. Specifically, *A154453 = psi(A154443), where the isomorphism psi is given in A153141 (see further comments there).

Links

Crossrefs

Inverse: A154454. a(n) = A154451(A069767(n)) = A057163(A154449(A057163(n))). Cf. A154455.
Differs from its inverse A154454 for the first time at n=49, where a(49)=63, while A154454(49)=64. Differs from A089854 for the first time at n=63, where a(63)=50, while A089854(63)=49. Differs from A131173 for the first time at n=26, where a(26)=26, while A131173(26)=27.

A154454 Signature permutation of a Catalan bijection: The inverse of A154453.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jan 17 2009

Keywords

Comments

This automorphism of rooted plane binary trees switches the two descendant trees for every other vertex as it descends along the 000... ray, but not starting swapping until at the left-hand side child of the root, leaving the root itself fixed. Specifically, *A154454 = psi(A154444), where the isomorphism psi is given in A153141 (see further comments there).

Links

Crossrefs

Inverse: A154453. a(n) = A069768(A154452(n)) = A057163(A154450(A057163(n))). Cf. A069770, A154456.
Differs from its inverse A154453 for the first time at n=49, where a(49)=64, while A154454(49)=63. Differs from A089854 for the first time at n=49, where a(49)=64, while A089854(49)=63. Differs from A131173 for the first time at n=26, where a(26)=26, while A131173(26)=27.

A089831 Triangle T(n,m) (read as T(1,1); T(2,1), T(2,2); T(3,1), T(3,2), T(3,3);) Number of distinct non-recursive Catalan Automorphisms whose minimum clause-representation requires examination of n nodes in total, divided into m non-default clauses.

Original entry on oeis.org

1, 10, 0, 115, 10, 0, 1666, 139, 0, 0, 30198, 2570, 0, 0, 0, 665148, 47878, 904, 0, 0, 0, 17296851, 1017174, 20972, 0, 0, 0, 0
Offset: 1

Views

Author

Antti Karttunen, Dec 05 2003

Keywords

Examples

			...... Triangle............................ Row sums
........1........................................1
.......10.......0...............................10
......115......10...0..........................125 = 5^3
.....1666.....139...0....0....................1805 = 5*19^2
....30198....2570...0....0...0...............32768 = 32^3 = 8^5
...665148...47878...904..0...0...0..........713930
.17296851.1017174.20972..0...0...0...0....18334997
T(1,1)=1, as there is just one non-identity, non-recursive Catalan bijection with a single non-default clause opening a single node, namely A089840[1]=A069770.
T(2,1)=10, as there are the following non-recursive Catalan bijections (rows 2-11 of A089840): A072796, A089850, A089851, A089852, A089853, A089854, A072797, A089855, A089856, A089857, whose minimum clause-representation consists of a single non-default clause that opens two nodes.
T(3,2)=10, as there are the following non-recursive Catalan bijections (rows 12-21 of A089840): A074679, A089858, A073269, A089859, A089860, A074680, A089861, A073270, A089862, A089863, whose minimum clause-representation consists of a two non-default clauses with total 3 nodes opened.

Links

Crossrefs

First column: A089833. Row sums: A089832. Row sums excluding the first column: A089834.
Showing 1-10 of 17 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.