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.

Previous Showing 11-20 of 26 results. Next

A079226 Number of Catalan objects fixed by five-fold application of the Catalan bijections A057511/A057512 (deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 3, 5, 6, 15, 36, 108, 301, 814, 2080, 5223, 12919, 32557, 83943, 222591, 600252, 1632814, 4440240, 12043224, 32572225, 88081208, 238722759, 649725756, 1776546687, 4877740703, 13432630929, 37063472432, 102389547753
Offset: 0

Views

Author

Antti Karttunen Jan 03 2002

Keywords

Crossrefs

The fifth row of A079216. The leftmost edge of the triangle A079221 and also its row sums shifted by one. Occurs in A073202 as row 9259542121261050623. Cf. A057546, A079223-A079227.

Programs

Formula

a(n) = A079216(n, 5)

A079221 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=0, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by the five-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 0, 1, 3, 1, 0, 1, 5, 0, 0, 0, 1, 6, 2, 1, 0, 5, 1, 15, 0, 0, 0, 20, 0, 1, 36, 5, 0, 1, 65, 0, 0, 1, 108, 0, 2, 0, 190, 0, 0, 0, 1, 301, 11, 0, 0, 501, 0, 0, 0, 0, 1, 814, 0, 0, 0, 1265, 0, 0, 0, 0, 0, 1, 2080, 26, 3, 2, 3105, 1, 0, 0, 0, 5, 0, 1, 5223, 0, 0, 0, 7695, 0, 0, 0, 0, 0, 0, 0
Offset: 0

Views

Author

Antti Karttunen Jan 03 2002

Keywords

Comments

Note: the counts given here are inclusive, i.e. T(n,d) includes also the count A079217(n,d).

Crossrefs

The row sums equal to the left edge shifted left once = A079226 = fifth row of A079216 (the latter gives the Maple procedure PFixedByA057511). Cf. also A079217-A079222 and A003056 and A002262.

Programs

A079224 Number of Catalan objects fixed by three-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 3, 8, 18, 43, 104, 273, 702, 1870, 4985, 13562, 37038, 102266, 283774, 793189, 2227115, 6286044, 17811751, 50672898, 144639235, 414181050, 1189365940, 3424477813, 9883578364, 28589660227, 82870288432, 240672107114
Offset: 0

Views

Author

Antti Karttunen Jan 03 2002

Keywords

Crossrefs

The third row of A079216. The leftmost edge of the triangle A079219 and also its row sums shifted by one. Occurs in A073202 as row 43639. Cf. A057546, A079223-A079227.

Programs

Formula

a(n) = A079216(n, 3)

A079225 Number of Catalan objects fixed by four-fold application of the Catalan bijections A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 2, 5, 11, 30, 82, 233, 680, 2033, 6164, 18923, 58768, 184045, 581105, 1846906, 5905364, 18980465, 61292929, 198758704, 646974285, 2113163707, 6923642271, 22749608810, 74946337830, 247499313730, 819154110660, 2716779932308
Offset: 0

Views

Author

Antti Karttunen Jan 03 2002

Keywords

Crossrefs

The fourth row of A079216. The leftmost edge of the triangle A079220 and also its row sums shifted by one. Occurs in A073202 as row 2290625151. Cf. A057546, A079223-A079227.

Programs

Formula

a(n) = A079216(n, 4)

A130920 Signature permutation of a Catalan automorphism: DEEPEN-transform of automorphism *A057512.

Original entry on oeis.org

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

Views

Author

Antti Karttunen, Jun 11 2007

Keywords

Comments

*A130920 = DEEPEN(*A057512) = NEPEED(*A057512) = DEEPEN(DEEPEN(*A057510)) = NEPEED(NEPEED(*A057510)). See A122283, A122284 for the definitions of DEEPEN and NEPEED transforms.

Links

Crossrefs

Inverse: A130919. A122351(n) = A083927(A130920(A057123(n))).

A079220 Triangle T(n,d) (listed row-wise: T(1,1)=1, T(2,1)=1, T(2,2)=1, T(3,1)=2, T(3,2)=2, T(3,3)=1, ...) giving the number of n-edge general plane trees with root degree d that are fixed by the four-fold application of Catalan Automorphisms A057511/A057512 (Deep rotation of general parenthesizations/plane trees).

Original entry on oeis.org

1, 1, 1, 2, 2, 1, 5, 5, 0, 1, 11, 14, 0, 4, 1, 30, 36, 1, 14, 0, 1, 82, 102, 0, 48, 0, 0, 1, 233, 293, 0, 153, 0, 0, 0, 1, 680, 860, 2, 488, 0, 2, 0, 0, 1, 2033, 2575, 0, 1550, 1, 0, 0, 4, 0, 1, 6164, 7838, 0, 4920, 0, 0, 0, 0, 0, 0, 1, 18923, 24148, 5, 15672, 0, 5, 0, 14, 0, 0, 0, 1
Offset: 0

Views

Author

Antti Karttunen Jan 03 2002

Keywords

Comments

Note: the counts given here are inclusive, i.e. T(n,d) includes also the count A079218(n,d).

Crossrefs

The row sums equal to the left edge shifted left once = A079225 = fourth row of A079216 (the latter gives the Maple procedure PFixedByA057511). Cf. also A079217-A079222 and A003056 & A002262.

Programs

A243495 Indices in A014486 for the oriented trees that stay the same when "deep-rotated": fixed points of A057511/A057512.

Original entry on oeis.org

0, 1, 2, 3, 4, 7, 8, 9, 15, 17, 21, 22, 23, 45, 55, 58, 63, 64, 65, 113, 124, 129, 153, 170, 185, 189, 195, 196, 197, 393, 493, 515, 524, 564, 591, 612, 617, 624, 625, 626, 1103, 1237, 1251, 1330, 1535, 1628, 1679, 1794, 1859, 1897, 1911, 1973, 2012, 2040, 2046, 2054, 2055
Offset: 0

Views

Author

Antti Karttunen, Jun 07 2014

Keywords

Crossrefs

Cf. A243496, A243497, A014486, A057511, A057512.

A073200 Number of simple Catalan bijections of type B.

Original entry on oeis.org

0, 1, 0, 3, 1, 0, 2, 2, 1, 0, 7, 3, 3, 1, 0, 8, 4, 2, 3, 1, 0, 6, 6, 8, 2, 3, 1, 0, 4, 5, 7, 7, 2, 3, 1, 0, 5, 7, 6, 6, 8, 2, 3, 1, 0, 17, 8, 5, 8, 7, 7, 2, 2, 1, 0, 18, 9, 4, 4, 6, 8, 7, 3, 3, 1, 0, 20, 10, 22, 5, 5, 5, 8, 4, 2, 2, 1, 0, 21, 14, 21, 17, 4, 4, 6, 5, 8, 3, 3, 1, 0
Offset: 0

Views

Author

Antti Karttunen, Jun 25 2002

Keywords

Comments

Each row is a permutation of nonnegative integers induced by a Catalan bijection (constructed as explained below) acting on the parenthesizations/plane binary trees as encoded and ordered by A014486/A063171.
The construction process is akin to the constructive mapping of primitive recursive functions to N: we have two basic primitives, A069770 (row 0) and A072796 (row 1), of which the former swaps the left and the right subtree of a binary tree and the latter exchanges the positions of the two leftmost subtrees of plane general trees, unless the tree's degree is less than 2, in which case it just fixes it. From then on, the even rows are constructed recursively from any other Catalan bijection in this table, using one of the five allowed recursion types:
0 - Apply the given Catalan bijection and then recurse down to both subtrees of the new binary tree obtained. (last decimal digit of row number = 2)
1 - First recurse down to both subtrees of the old binary tree and only after that apply the given Catalan bijection. (last digit = 4)
2 - Apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree obtained. (last digit = 6)
3 - First recurse down to the right subtree of old binary tree and only after that apply the given Catalan bijection. (last digit = 8)
4 - First recurse down to the left subtree of old binary tree, after that apply the given Catalan bijection and then recurse down to the right subtree of the new binary tree. (last digit = 0)
The odd rows > 2 are compositions of the rows 0, 1, 2, 4, 6, 8, ... (i.e. either one of the primitives A069770 or A072796, or one of the recursive compositions) at the left hand side and any Catalan bijection from the same array at the right hand side. See the scheme-functions index-for-recursive-sgtb and index-for-composed-sgtb how to compute the positions of the recursive and ordinary compositions in this table.

Links

  • A. Karttunen, Gatomorphisms (With the complete source and explanation)

Crossrefs

Four other tables giving the corresponding cycle-counts: A073201, counts of the fixed elements: A073202, the lengths of the largest cycles: A073203, the LCM's of all the cycles: A073204. The ordinary compositions are encoded using the N X N -> N bijection A054238 (which in turn uses the bit-interleaving function A000695).
The first 21 rows of this table:.
Row 0: A069770. Row 1: A072796. Row 2: A057163. Row 3: A073269, Row 4: A057163 (duplicate), Row 5: A073270, Row 6: A069767, Row 7: A001477 (identity perm.), Row 8: A069768, Row 9: A073280.
Row 10: A069770 (dupl.), Row 11: A072796 (dupl.), Row 12: A057511, Row 13: A073282, Row 14: A057512, Row 15: A073281, Row 16: A057509, Row 17: A073280 (dupl.), Row 18: A057510, Row 19: A073283, Row 20: A073284.
Other Catalan bijection-induced EIS-permutations which occur in this table. Only the first known occurrence is given. Involutions are marked with *, others paired with their inverse:.
Row 164: A057164*, Row 168: A057508*, Row 179: A072797*.
Row 41: A073286 - Row 69: A073287. Row 105: A073290 - Row 197: A073291. Row 416: A073288 - Row 696: A073289.
Row 261: A057501 - Row 521: A057502. Row 2618: A057503 - Row 5216: A057504. Row 2614: A057505 - Row 5212: A057506.
Row 10435: A073292 - Row ...: A073293. Row 17517: A057161 - Row ...: A057162.
For a more practical enumeration system of (some) Catalan automorphisms see table A089840 and its various "recursive derivations".

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

A122202 Signature permutations of KROF-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, 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
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 "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

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.
Previous Showing 11-20 of 26 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.