A089840 -id:A089840 - cp's OEIS frontend

A122285 Signature permutations of ENIPS-transformations of Catalan automorphisms in table A122203.

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, 11, 12, 13

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122203 with the recursion scheme "ENIPS", or equivalently row n is obtained as ENIPS(SPINE(n-th row of A089840)). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A122286. This table contains also all the rows of A122204 and A089840.

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

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082348, 2: A057508, 3: A131141, 4: A131143, 5: A131145, 6: A131147, 7: A131173, 8: A131169, 9: A131149, 10: A131151, 11: A131153, 12: A131171, 13: A131155, 14: A131157, 15: A131159, 16: A131161, 17: A057503, 18: A131163, 19: A131165, 20: A131167, 21: A069768. Other rows: row 251: A130360, 3608: A130339, 3613: A057510, 65352: A074686.

See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122286-A122288, A122289-A122290, A130400-A130403. As a sequence differs from A122286 for the first time at n=92, where a(n)=18, while A122286(n)=17.

A122288 Signature permutations of KROF-transformations of Catalan automorphisms in table A122203.

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, 11, 12, 13

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122203 with the recursion scheme "KROF", or equivalently row n is obtained as KROF(SPINE(n-th row of A089840)). See A122202 and A122203 for the description of KROF and SPINE. Moreover, each row of A122288 can be obtained as the "NEPEED" transform of the corresponding row in A122285. (See A122284 for the description of NEPEED). Each row occurs only once in this table. Inverses of these permutations can be found in table A122287. This table contains also all the rows of A122202 and A089840.

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

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069768, 2: A057164, 3: A130981, 4: A130983, 5: A130982, 6: A130984, 7: A130985, 8: A130987, 9: A130989, 10: A130991, 11: A130993, 12: A131009, 13: A130995, 14: A130997, 15: A130999, 16: A131001, 17: A057505, 18: A131003, 19: A131005, 20: A131007, 21: A057163. Other rows: 251: A122354, 3613: A057512, 65352: A074682.

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Jun 12 2002

nonn

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).
   A   B           A   C
    \ /             \ /
     x   C    -->    x   B               ()  A        ()   A
      \ /             \ /                 \ /    -->    \ /
       x               x                   x             x
  ((a . b) . c) --> ((a . c) . b)      (() . a) ---> (() . a)
See the example for an explanation of how to obtain a given integer sequence from this definition.
Notably for this permutation, A127301(a(n)) = A127301(n) does not always hold, even though for all n, A129593(a(n)) = A129593(n). - Antti Karttunen, Jan 14 2024

			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 "B" and "C" in the diagram given in the comments are:
.
                          \/     \/       \/               \/
       \/     \/         \/       \/     \/       \/ \/     \/
      \/       \/       \/       \/       \/       \_/       \/
a(n)=  2        3        4        5        7        6        8
thus we obtain the first nine terms of this sequence: 0, 1, 2, 3, 4, 5, 7, 6, 8.

Row 8 of A089840.
Cf. A014486, A057163, A072796, A127301, A129593.
Counts for the fixed points and for the number of distinct cycles (in each subrange limited by A014137) are given by A073190 and A073191.

a(n) = A057163(A072796(A057163(n))).

Further comments added by Antti Karttunen, Jun 04 2011 and Mar 30 2024

A130403 Signature permutations of SPINE-transformations of A057163-conjugates of Catalan automorphisms in table A122204.

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, 5, 4, 3, 2, 1, 0, 8, 4, 7, 5, 4, 3, 2, 1, 0, 9, 5, 6, 6, 5, 4, 3, 2, 1, 0, 10, 17, 8, 8, 8, 5, 4, 3, 2, 1, 0, 11, 18, 9, 7, 6, 8, 5, 5, 3, 2, 1, 0, 12, 20, 10, 9, 7, 7, 7, 4, 4, 3, 2, 1, 0, 13, 21, 12, 10, 9, 6

Offset: 0

Antti Karttunen, Jun 11 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from A057163-conjugate of the n-th automorphism in the table A122204 with the recursion scheme "SPINE", i.e. row n is obtained as SPINE(A057163 o ENIPS(A089840[n]) o A057163). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A130402. This table contains also all the rows of A122203 and A089840.

Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082345, 2: A130936, 3: A073288, 4: A130942, 5: A130940, 6: A130938, 7: A130944, 8: A130946, 9: A130952, 10: A130950, 11: A130948, 12: A057161, 13: A130962, 14: A130964, 15: A069767, 16: A130966, 17: A074688, 18: A130954, 19: A130956, 20: A130960, 21: A130958, Other rows: 169: A069770, 3617: A082339, 65167: A057501.
Cf. also tables A089840, A122201-A122204, A122285-A122286, A130400-A130401.
Cf. As a sequence differs from A130403 for the first time at n=92, where a(n)=21, while A130403(n)=22.

A122286 Signature permutations of SPINE-transformations of Catalan automorphisms in table A122204.

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, 17, 11, 12, 13

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122204 with the recursion scheme "SPINE", or equivalently row n is obtained as SPINE(ENIPS(n-th row of A089840)). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A122285. This table contains also all the rows of A122203 and A089840.

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

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082347, 2: A057508, 3: A131142, 4: A131148, 5: A131146, 6: A131144, 7: A131173, 8: A131170, 9: A131154, 10: A131152, 11: A131150, 12: A057504, 13: A131164, 14: A131166, 15: A069767, 16: A131168, 17: A131172, 18: A131156, 19: A131158, 20: A131162, 21: A131160. Other rows: row 169: A130359, 3608: A130339, 3617: A057509, 65167: A074685.

See also tables A089840, A122200, A122201-A122204, A122283-A122284, A122285-A122288, A122289-A122290, A130400-A130403. As a sequence differs from A122285 for the first time at n=92, where a(n)=17, while A122285(n)=18.

A122287 Signature permutations of FORK-transformations of Catalan automorphisms in table A122204.

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

Offset: 0

Antti Karttunen, Sep 01 2006, Jun 20 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from the n-th automorphism in the table A122204 with the recursion scheme "FORK", or equivalently row n is obtained as FORK(ENIPS(n-th row of A089840)). See A122201 and A122204 for the description of FORK and ENIPS. Moreover, each row of A122287 can be obtained as the "DEEPEN" transform of the corresponding row in A122286. (See A122283 for the description of DEEPEN). Each row occurs only once in this table. Inverses of these permutations can be found in table A122288. This table contains also all the rows of A122201 and A089840.

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

Index entries for signature-permutations of Catalan automorphisms

The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A069767, 2: A057164, 3: A130981, 4: A130983, 5: A130982, 6: A130984, 7: A130986, 8: A130988, 9: A130994, 10: A130992, 11: A130990, 12: A057506, 13: A131004, 14: A131006, 15: A057163, 16: A131008, 17: A131010, 18: A130996, 19: A130998, 20: A131002, 21: A131000. Other rows: 169: A122353, 3617: A057511, 65167: A074681.

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

Antti Karttunen, Nov 29 2003

nonn

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.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

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).

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

A130402 Signature permutations of ENIPS-transformations of A057163-conjugates of Catalan automorphisms in table A122203.

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, 5, 4, 3, 2, 1, 0, 8, 4, 7, 5, 4, 3, 2, 1, 0, 9, 5, 6, 6, 5, 4, 3, 2, 1, 0, 10, 17, 8, 8, 8, 5, 4, 3, 2, 1, 0, 11, 18, 9, 7, 6, 8, 5, 5, 3, 2, 1, 0, 12, 20, 10, 9, 7, 7, 7, 4, 4, 3, 2, 1, 0, 13, 22, 12, 10, 9, 6

Offset: 0

Antti Karttunen, Jun 11 2007

Row n is the signature permutation of the Catalan automorphism which is obtained from A057163-conjugate of the n-th automorphism in the table A122203 with the recursion scheme "ENIPS", i.e. row n is obtained as ENIPS(A057163 o SPINE(A089840[n]) o A057163). See A122203 and A122204 for the description of SPINE and ENIPS. Each row occurs only once in this table. Inverses of these permutations can be found in table A130403. This table contains also all the rows of A122204 and A089840.

Cf. The first 22 rows of this table: row 0 (identity permutation): A001477, 1: A082346, 2: A130935, 3: A073289, 4: A130937, 5: A130939, 6: A130941, 7: A130943, 8: A130945, 9: A130947, 10: A130949, 11: A130951, 12: A074687, 13: A130953, 14: A130955, 15: A130957, 16: A130959, 17: A057162, 18: A130961, 19: A130963, 20: A130965, 21: A069768. Other rows: 251: A069770, 3613: A082340, 65352: A057502.
Cf. also tables A089840, A122201-A122204, A122285-A122286, A130400-A130401.
Cf. As a sequence differs from A130403 for the first time at n=92, where a(n)=22, while A130403(n)=21.

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

Original entry on oeis.org

0, 1, 2, 3, 5, 6, 4, 7, 8, 12, 13, 15, 16, 19, 11, 14, 9, 17, 18, 10, 20, 21, 22, 31, 32, 34, 35, 36, 40, 41, 43, 44, 47, 52, 53, 56, 60, 30, 33, 39, 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, 87, 88, 90, 91, 92, 96, 97, 99

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

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....-->....B...x.................A..().........A...()..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> (b . (c . a)) ____ (a . ()) ---> (a . ())
In terms of S-expressions, this rotates car, cadr and cddr of an S-exp
if its length > 1, otherwise keeps it intact.
Note that the first clause corresponds to generator C of Thompson's groups T and V.
(Cf. also A072796, A074679 and A154121 for other related generators).
See "Catalan Automorphisms" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

Inverse of A089853. a(n) = A089850(A072796(n)) = A057163(A089857(A057163(n))). Row 4 of A089840.

Number of cycles: A089847. Number of fixed-points: A089848 (in each range limited by A014137 and A014138).

The new mail-address, further comments and constructive implementation of Scheme-function (*A089851) 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

Antti Karttunen, Nov 29 2003

nonn

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.

A. Karttunen, Catalan Automorphisms
A. Karttunen, C-program for computing this sequence
Index entries for signature-permutations induced by Catalan automorphisms

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).

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

cp's OEIS Frontend

A122285 Signature permutations of ENIPS-transformations of Catalan automorphisms in table A122203.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A122288 Signature permutations of KROF-transformations of Catalan automorphisms in table A122203.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A072797 Self-inverse permutation of natural numbers induced by a Catalan bijection acting on binary trees as encoded by A014486. See comments and examples for details.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A130403 Signature permutations of SPINE-transformations of A057163-conjugates of Catalan automorphisms in table A122204.

Views

Author

Keywords

Comments

Crossrefs

A122286 Signature permutations of SPINE-transformations of Catalan automorphisms in table A122204.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A122287 Signature permutations of FORK-transformations of Catalan automorphisms in table A122204.

Views

Author

Keywords

Comments

References

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A130402 Signature permutations of ENIPS-transformations of A057163-conjugates of Catalan automorphisms in table A122203.

Views

Author

Keywords

Comments

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions