A089408 -id:A089408 - cp's OEIS frontend

A079438 a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

1, 1, 2, 2, 2, 4, 4, 4, 6, 6, 6, 8, 8, 8, 12, 12, 12, 14, 16, 16, 18, 18, 22, 24, 24, 24, 28, 28, 28, 30, 34, 34, 36, 36, 38, 40, 40, 40, 46, 46, 46, 48, 50, 50, 52, 52, 56, 58, 58, 58, 62, 62, 62, 64, 68, 68, 70, 70, 72, 74, 74, 74, 80, 80, 80, 82, 84, 84, 86, 86, 90, 92, 92, 92

Offset: 0

Antti Karttunen, Jan 27 2003

nonn

The original definition was: Number of rooted general plane trees which are symmetric and will stay symmetric after the underlying plane binary tree has been reflected, i.e., number of integers i in range [A014137(n-1)..A014138(n-1)] such that A057164(i) = i and A057164(A057163(i)) = A057163(i).
(Thus also) the number of fixed points in range [A014137(n-1)..A014138(n)] of permutation A071661 (= Donaghey's automorphism M "squared"), which is equal to condition A057164(i) = A069787(i) = i, i.e., the size of the intersection of fixed points of permutations A057164 and A069787 in the same range.
Additional comment from Antti Karttunen, Dec 13 2017: (Start)
However, David Callan's A123050 claims to give more correct version of that count from n=26 onward, so I probably made a little mistake when converting my insights into the formula given here. At that time I reckoned that if the conjecture given in A080070 were true, then it would imply that the formula given here were exact, otherwise it would give only a lower bound.
It would be nice to know what an empirical program would give as the count of fixed points of A071661 for n in range [A014137(25)..A014138(26)] = [6619846420553 .. 24987199492704], with total A000108(26) = 18367353072151 points to check.
(End)

D. E. Knuth, The Art of Computer Programming, Volume 4, Fascicle 4: Generating All Trees--History of Combinatorial Generation, vi+120pp. ISBN 0-321-33570-8 Addison-Wesley Professional; 1ST edition (Feb 06, 2006).

G. C. Greubel, Table of n, a(n) for n = 0..10000
R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
A. Karttunen, C-program for counting the initial terms of this sequence (empirically)
A. Karttunen, Illustration of initial terms for trees of sizes n=2..18
A. Karttunen, On the fixed points of A071661 (Notes in OEIS Wiki)
D. E. Knuth, Pre-Fascicle 4a: Generating All Trees, Exercise 17, 7.2.1.6.

Cf. A000108, A057163, A057164, A057505, A069787, A071661, A079437, A079439, A079442, A080070, A243490,  A243491, A243492.
From n>= 2 onward A079440(n) = a(n)/2.
Occurs in A073202 as row 13373289.
Differs from A123050 for the first time at n=26.

A079438 := n -> `if`((n<2),1,2*(floor((n+1)/3) + `if`((n>=14),floor((n-10)/4)+floor((n-14)/8),0)));

a[0]:= 1; a[1]:= 1; a[n_]:= a[n] = 2*Floor[(n+1)/3] +2*If[ n >= 14, (Floor[(n-10)/4] +Floor[(n-14)/8]), 0]; Table[a[n], {n, 0, 100}] (* G. C. Greubel, Jan 18 2019 *)

{a(n) = if(n==0, 1, if(n==1, 1, 2*floor((n+1)/3) + 2*if(n >= 14, floor( (n-10)/4) + floor((n-14)/8), 0)))}; \\ G. C. Greubel, Jan 18 2019

a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

Entry edited (the definition replaced by a formula, the old definition moved to the comments) - Antti Karttunen, Dec 13 2017

A060114 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

1, 1, 2, 6, 6, 30, 120, 720, 15120, 1164240, 15135120, 283931716867999200, 14510088480716327580681600, 3280681990411073806237542217555200, 936436634805345771521186435213604447980767985241556128000

Offset: 0

Antti Karttunen, Mar 01 2001

nonn

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.

This sequence grows so fast that it seems hopeless to count A057507 with Burnside's (orbit-counting) lemma.

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

Cf. A057505, A057507, A057545, A081165, A081166, A078491.

Occurs for first time in A073204 as row 2614.

A086586 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutations A074681/A074682 & A074683/A074684.

Original entry on oeis.org

1, 1, 2, 5, 9, 28, 57, 253, 842, 3753, 10927, 15014, 130831, 218961, 967104, 3767216, 29715310, 89923607, 314897868, 785059994

Offset: 0

Antti Karttunen, Jun 23 2003

Shifted once right (beginning as 1,1,1,2,5,9,...) this is maximum cycle size (in the same range) of permutations A085169/A085170, shifted twice right (beginning as 1,1,1,1,2,5,9,...) this is the maximum cycle size in permutations A089867/A089868 and A089869/A089870.

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

A057504 Signature-permutation of the inverse of Deutsch's 1998 bijection on Dyck paths.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

Emeric Deutsch, A bijection on Dyck paths and its consequences, Discrete Math., 179 (1998), 253-256.
Antti Karttunen, C program which computes this sequence.
Index entries for signature-permutations of Catalan automorphisms

Inverse: A057503. Row 12 of A122286.

A080237(n) = A057515(a(n)) holds for all n. See comment at A057503.

Equivalence with Deutsch's 1998 bijection realized Dec 15 2006 and entry edited accordingly by Antti Karttunen, Jan 16 2007

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

A079442 Number of fixed points in range [A014137(n-1)..A014138(n)] of permutation A071663.

Original entry on oeis.org

1, 1, 0, 3, 0, 9, 0, 21, 0, 45, 0, 99, 0, 195, 0, 399, 0, 801, 0

Offset: 0

Antti Karttunen, Jan 27 2003

R. Donaghey, Automorphisms on Catalan trees and bracketing, J. Combin. Theory, Series B, 29 (1980), 75-90.
Antti Karttunen, C-program for counting the initial terms of this sequence
Antti Karttunen, Illustration of initial terms for trees of sizes n=3..11

Cf. A057505, A071663, A079438, A079441, A079443, A079444.

Occurs in A073202 as row 176609070820803.

For all n >= 0, a(2n+3)/3 = A079444(n).

Name corrected by Antti Karttunen, Dec 13 2017

A081150 Number of even cycles in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Original entry on oeis.org

0, 0, 1, 1, 3, 6, 18, 37, 95, 212, 528, 1226, 2936, 6822, 16212, 38081, 90717, 215414, 516358

Offset: 0

Wouter Meeussen and Antti Karttunen, Mar 10 2003

For the convenience of the range notation above, we define A014137(-1) and A014138(-1) as zero.

Antti Karttunen, Counted with the help of this C program.

Bisections: A081151, A081152.
Cf. A081157, A081160, A081162, A057507, A081148.
Cf. A014137, A014138, A057505, A057506.

a(n) = A081157(n) + A081160(n) + A081162(n) = A057507(n) - A081148(n).

A089410 Least common multiple of all cycle sizes (also the maximum cycle size) in range [A014137(n-1)..A014138(n-1)] of permutation A074679/A074680.

Original entry on oeis.org

1, 1, 2, 5, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, 66, 70, 74, 78

Offset: 0

Antti Karttunen, Nov 29 2003

nonn

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

Cf. A016825.

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

cp's OEIS Frontend

A079438 a(0) = a(1) = 1, a(n) = 2*(floor((n+1)/3) + (if n >= 14) (floor((n-10)/4) + floor((n-14)/8))).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A060114 Least common multiple of all cycle sizes in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

A086586 Maximum cycle size in range [A014137(n-1)..A014138(n-1)] of permutations A074681/A074682 & A074683/A074684.

Views

Author

Keywords

Comments

Links

A057504 Signature-permutation of the inverse of Deutsch's 1998 bijection on Dyck paths.

Views

Author

Keywords

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

A079442 Number of fixed points in range [A014137(n-1)..A014138(n)] of permutation A071663.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A081150 Number of even cycles in range [A014137(n-1)..A014138(n-1)] of permutation A057505/A057506.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A089410 Least common multiple of all cycle sizes (also the maximum cycle size) in range [A014137(n-1)..A014138(n-1)] of permutation A074679/A074680.

Views

Author

Keywords

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