A089865 -id:A089865 - cp's OEIS frontend

A089844 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A089865/A089866.

1, 1, 2, 4, 9, 23, 68, 205, 655, 2147, 7218, 24686, 85760, 301458, 1070820, 3836693, 13851191, 50333389, 183965474, 675825400, 2494114694

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

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

A. Karttunen, C-program for computing the initial terms of this sequence

A089845 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A089865/A089866.

Original entry on oeis.org

1, 1, 1, 2, 10, 70, 630, 6930, 90090, 90090, 1531530, 29099070, 29099070, 669278610, 3346393050, 10039179150, 291136195350, 9025222055850, 9025222055850, 9025222055850, 333933216066450

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

A. Karttunen, C-program for computing the initial terms of this sequence

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

Antti Karttunen, Dec 05 2003; last revised Jan 06 2009

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.

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

A. Karttunen, C-program for computing the terms of this table. Defines also the order of rows.
A. Karttunen, Prolog-program which illustrates the construction of each row

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.

A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 11 2002

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.......A...B
....\./.........\./
.A...x....-->....x...C.................A..().........()..A..
..\./.............\./...................\./....-->....\./...
...x...............x.....................x.............x....
(a . (b . c)) -> ((a . b) . c) ____ (a . ()) --> (() . a)
That is, we rotate the binary tree left, in case it is possible and otherwise (if the right hand side of a tree is a terminal node) swap the left and right subtree (so that the terminal node ends to the left hand side), i.e., apply the automorphism *A069770. Look at the example in A069770 to see how this will produce the given sequence of integers.
This is the first multiclause nonrecursive automorphism in table A089840 and the first one whose order is not finite, i.e., the maximum size of cycles in this permutation is not bounded (see A089842). The cycle counts in range [A014137(n-1)..A014138(n)] of this permutation is given by A001683(n+1), which is otherwise the same sequence as for Catalan automorphisms *A057161/*A057162, but shifted once right. For an explanation, please see the notes in OEIS Wiki.

A. Karttunen, Table of n, a(n) for n = 0..2055
A. Karttunen, Introductory Survey of Catalan Automorphisms and Bijections, (an unfinished draft)
A. Karttunen, Notes on the orbits of this permutation, OEIS Wiki.
A. Karttunen, Prolog-program which illustrates the construction of this and similar nonrecursive bijections of oriented binary trees
Index entries for signature-permutations of Catalan automorphisms

This automorphism has several variants, where the first clause is same (rotate binary tree to the left, if possible), but something else is done (than just swapping sides), in case the right hand side is empty: A082335, A082349, A123499, A123695. The following automorphisms can be derived recursively from this one: A057502, A074681, A074683, A074685, A074687, A074690, A089865, A120706, A122321, A122332. See also somewhat similar ones: A069773, A071660, A071656, A071658, A072091, A072095, A072093.
Inverse: A074680.
Row 12 of A089840.
Occurs also in A073200 as row 557243 because a(n) = A073283(A073280(A072796(n))). a(n) = A083927(A123498(A057123(n))).
Number of cycles: LEFT(A001683). Number of fixed points: LEFT(A019590). Max. cycle size & LCM of all cycle sizes: A089410 (in range [A014137(n-1)..A014138(n)] of this permutation).

Description clarified Oct 10 2006

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

Antti Karttunen, Jan 06 2009

nonn

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

A. Karttunen, Table of n, a(n) for n = 0..2055
J. W. Cannon, W. J. Floyd, and W. R. Parry, Notes on Richard Thompson's Groups F and T
J. W. Cannon, W. J. Floyd, and W. R. Parry, Introductory notes on Richard Thompson's groups, L'Enseignement Mathématique, Vol. 42 (1996), pp. 215-256.
A. Karttunen, On the connection of A089840 with Thompson's groups, speculation and conjectures.
Index entries for signature-permutations of Catalan automorphisms

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

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

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, 17, 18, 20, 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, 44, 45, 46, 47, 48, 49, 50, 53, 54, 55, 57, 61, 65, 66, 67, 68, 69

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

This bijection of binary trees is obtained when we apply bijection *A074680 to the left subtree and keep the right subtree intact.
.A...B...............B...C
..\./.................\./
...x...C....-->....A...x.................()..B.........B...()....
....\./.............\./...................\./....-->....\./.....
.....x...D...........x...D.................x...C.........x...C..
......\./.............\./...................\./...........\./...
.......x...............x.....................x.............x....
................................................................
Compare to A154122.
See "Catalan bijections" OEIS-Wiki page for a detailed explanation how to obtain a given integer sequence from this definition.

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

Row 4299 of A089840. Inverse of A089865. a(n) = A069770(A154122(A069770(n))).

Number of cycles: A089844. Number of fixed-points: A005807 (prepended with two 1's). Max. cycle size: A089410. LCM of cycle sizes: A089845 (in each range limited by A014137 and A014138).

Further comments and constructive version of Scheme-implementation added by Antti Karttunen, Jun 04 2011

A123694 a(n) gives the A089840-index of the nonrecursive Catalan automorphism which is formed from A089840[n] by applying it to the left subtree of a binary tree and leaving the right-hand side subtree intact.

Original entry on oeis.org

0, 7, 91, 92, 93, 94, 95, 114, 115, 116, 117, 118, 4207, 4209, 4211, 4214, 4216, 4299, 4301, 4303, 4305, 4307, 1228, 1229, 1230, 1231, 1232, 1233, 1234, 1235, 1236, 1237, 1238, 1239, 1240, 1241, 1242, 1243, 1244, 1245, 1246, 1247, 1248, 1249, 1250, 1347

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

If the count of fixed points of the automorphism A089840[n] is given by sequence f, then the count of fixed points of the automorphism A089840[A123694(n)] is given by CONV(f,A000108) (where CONV stands for convolution). See also the comments at A122200.

			When A089840[1] = A069770 (swap binary tree sides) is applied to the left subtree of a binary tree, we get A089840[7] = A089854, thus a(1)=7. When A089840[12] = A074679 is applied to the left subtree of a binary tree, we get A089840[4207] = A089865, thus a(12)=4207.

A. Karttunen, C-program for computing the initial terms of this sequence
A. Karttunen, Prolog-program which illustrates the nonrecursive Catalan automorphisms given on example-lines.

cp's OEIS Frontend

A089844 Number of cycles in range [A014137(n-1)..A014138(n-1)] of permutation A089865/A089866.

Views

Author

Keywords

Comments

Links

A089845 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A089865/A089866.

Views

Author

Keywords

Links

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.

Views

Author

Keywords

Comments

References

Links

Crossrefs

A074679 Signature permutation of a Catalan automorphism: Rotate binary tree left if possible, otherwise swap its sides.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A123694 a(n) gives the A089840-index of the nonrecursive Catalan automorphism which is formed from A089840[n] by applying it to the left subtree of a binary tree and leaving the right-hand side subtree intact.

Views

Author

Keywords

Comments

Examples

Links