A089840 -id:A089840 - cp's OEIS frontend

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

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

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.......B...A
......\./.........\./
...A...x...-->... .x...C...............A..().........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((b . a) . c) ____ (a . ()) ---> (() . a)
See the Karttunen OEIS-Wiki link 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

Row 13 of A089840. Inverse of A089861. a(n) = A072797(A069770(n)) = A069770(A089852(n)) = A057163(A073270(A057163(n))).

Number of cycles: A073193. Number of fixed-points: A019590. Max. cycle size: A089422. LCM of cycle sizes: A089423 (in each range limited by A014137 and A014138).

Further comments and constructive implementation of Scheme-function (*A089858) 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

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

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

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

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

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

Original entry on oeis.org

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

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...............A...C
..\./.................\./
...x...C...-->.....B...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (b . (a . c)) __ (() . 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 18 of A089840. Inverse of A089858. a(n) = A089852(A069770(n)) = A069770(A072797(n)) = A057163(A073269(A057163(n))).

Number of cycles: A073193. Number of fixed-points: A019590. Max. cycle size: A089422. LCM of cycle sizes: A089423 (in each range limited by A014137 and A014138).

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

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

Original entry on oeis.org

0, 1, 3, 2, 7, 8, 5, 6, 4, 17, 18, 20, 21, 22, 12, 13, 15, 16, 19, 11, 14, 9, 10, 45, 46, 48, 49, 50, 54, 55, 57, 58, 59, 61, 62, 63, 64, 31, 32, 34, 35, 36, 40, 41, 43, 44, 47, 52, 53, 56, 60, 30, 33, 39, 42, 51, 28, 37, 23, 24, 29, 38, 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...............C...A
..\./.................\./
...x...C...-->.....B...x...............()..A.........A..()..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) --> (b . (c . 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 20 of A089840. Inverse of A089860. a(n) = A089853(A069770(n)) = A069770(A089857(n)) = A069770(A074679(A069770(n))) = A057163(A089860(A057163(n))). Number of cycles: A001683 (seems to be, not checked). Number of fixed points: A019590. Max. cycle size & LCM of all cycle sizes: A089410 (in each range limited by A014137 and A014138).

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

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

Original entry on oeis.org

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

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...........C...B
..\./.............\./
...x...C....-->....x...A...............()..A.........()..A..
....\./.............\./.................\./....-->....\./...
.....x...............x...................x.............x....
((a . b) . c) -> ((c . b) . a) ___ (() . a) ---> (() . a)
In terms of S-expressions, this automorphism swaps caar and cdr of an S-exp if possible, i.e., if car-side is not ().
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 10 of A089840. a(n) = A073269(A069770(n)) = A069770(A073270(n)) = A057163(A089852(A057163(n))).

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

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

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

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

This "Catalan bijection" effects the following transformation on the binary trees (labels A,B,C,D refer to arbitrary subtrees located on those nodes and () stands for a terminal node.)
.A..B.C..D.....B..A.D..C.......B...C.......C...B.......A...B........B...A...
..\./.\./.......\./.\./.........\./.........\./.........\./..........\./....
...x...x....-->..x...x.......()..x..-->..()..x...........x..()...-->..x..().
....\./...........\./.........\./.........\./.............\./..........\./..
.....x.............x...........x...........x...............x............x...
i.e. we apply A069770 (that is, the corresponding automorphism) both to the left and right subtree of a binary tree and fix both the empty tree and the tree of one internal node.

			To obtain this 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 transforms to, as follows:
...................one tree of one internal........2 trees of 2 internal nodes
..empty tree.........(non-leaf) node.................................
........................................................\/.......\/..
......x......................\/........................\/.........\/.
n=....0......................1..........................2..........3.
a(n)=.0......................1..........................2..........3.(all these trees are fixed by this transformation)
however, the next 5 trees, with 3 internal nodes, in range [A014137[2], A014138[2]] = [4,8] change as follows:
........\/.....\/.................\/.....\/...
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
n=.....4........5........6........7........8..
....................|.........................
....................|.........................
....................V.........................
......\/.........\/.............\/.........\/.
.......\/.......\/.....\/.\/.....\/.......\/..
......\/.......\/.......\_/.......\/.......\/.
a(n)=..5........4........6........8........7..
thus we obtain the first nine terms of this sequence: 0,1,2,3,5,4,6,8,7,...

a(n) = A089859(A089859(n)) = A089863(A089863(n)). Row 1654694 of A089840.

Number of cycles: A089402. Number of fixed points: A089408. Max. cycle size & LCM of all cycle sizes: A046698 (in range [A014137(n-1)..A014138(n-1)] of this permutation).

A089865 Permutation of natural numbers induced by Catalan Automorphism *A089865 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, 20, 21, 16, 22, 17, 18, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 51, 52, 53, 54, 55, 56, 57, 58, 59, 42, 43, 60, 61, 62, 44, 63, 45, 46, 47, 64, 48, 49, 50, 65, 66, 67, 68, 69

Offset: 0

Antti Karttunen, Dec 20 2003

nonn

This bijection of binary trees is obtained when we apply bijection *A074679 to the left subtree and keep the right subtree intact.
....B...C.......A...B
.....\./.........\./
..A...x....-->....x...C.................A..().........()..A....
...\./.............\./...................\./....-->....\./.....
....x...D...........x...D.................x...C.........x...C..
.....\./.............\./...................\./...........\./...
......x...............x.....................x.............x....
...............................................................
Compare to A154121.
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

Row 4207 of A089840. Inverse of A089866. a(n) = A069770(A154121(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

A123492 An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism which swaps the sides of a binary tree if the left subtree of either the left or right hand side toplevel subtree is not empty and otherwise keeps the binary tree intact.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Oct 11 2006

nonn

This automorphism effects the following transformation on the unlabeled rooted plane binary trees (letters A, B, C and D refer to arbitrary subtrees located on those nodes.)
.....B...C.....B...C...........A...B.............A...B...
......\./.......\./.............\./...............\./....
.......x...D.....x...D...........x...C.............x...C.
........\./.......\./.............\./...............\./..
.....A...x...-->...x...A...........x...D...-->...D...x...
......\./...........\./.............\./...........\./....
.......x.............x...............x.............x.....

Row 79361 of A089840. Used to construct A123493, A123494, A123715 and A123716. Cf. A069770.

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

A089835 a(n) = (A000108(n)^2)*(n+1)!.

Original entry on oeis.org

1, 2, 24, 600, 23520, 1270080, 87816960, 7420533120, 742053312000, 85781362867200, 11260753452748800, 1655330757554073600, 269436914075724595200, 48113734656379392000000

Offset: 0

Antti Karttunen, Dec 05 2003

nonn

This sequence gives the total number of non-recursive "clauses" of n opening nodes, used in the construction of A089840.

INVERTi transform of A089836.

Cf. A000108, A000142, A001246, A001813.

a(n) = A001246(n)*A000142(n+1) = A001813(n)*A000108(n).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A123492 An involution of nonnegative integers: signature permutation of a nonrecursive Catalan automorphism which swaps the sides of a binary tree if the left subtree of either the left or right hand side toplevel subtree is not empty and otherwise keeps the binary tree intact.

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

A089835 a(n) = (A000108(n)^2)*(n+1)!.

Views

Author

Keywords

Comments

Crossrefs

Formula