A034731 -id:A034731 - cp's OEIS frontend

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

1, 1, 2, 3, 5, 6, 10, 11, 18, 21, 34, 35, 68, 69, 137, 148, 316, 317, 759, 760, 1869, 1915, 4833, 4834, 12796, 12802, 34108, 34384, 92792, 92793, 254752, 254753, 703083, 704956, 1958210, 1958231, 5485330, 5485331, 15427026, 15440591, 43618394, 43618395, 123807695, 123807696, 352561832, 352664217, 1007481494, 1007481495, 2887387009

Offset: 0

Antti Karttunen, Sep 07 2000

nonn

Greater than A003238 because there exists also parenthesizations like ((() (())) ((()) ())) and (((()) ()) (() (()))) which are fixed by recursive deep rotation, corresponding to Catalan mountain ranges below:
...../\..../\............................./\......../\
../\/\../\/\.....and.its."dual"....../\/\../\/\
./____\/____\......................./____\/____\
It's obvious that a(p) = a(p-1)+1 for all primes p.

Index entries for sequences related to parenthesizing

The first row of A079216. The leftmost edge of the triangle A079217 and also its row sums shifted by one. Occurs for first time in A073202 as row 12. Cf. A057513, A079223-A079227, A034731, A003238.

with(numtheory,divisors); A057546 := proc(n) local d; if(0=n) then RETURN(1); else RETURN(add(A079216bi(d-1,n/d),d=divisors(n))); fi; end;

a(0)=1, a(n) = A079216(n, 1) = Sum_{d|n} A079216(d-1, n/d). - Antti Karttunen, Jan 03 2003

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Original entry on oeis.org

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

Offset: 0

Antti Karttunen, Sep 03 2000

nonn

The number of objects (rooted planar trees, mountain ranges, parenthesizations) fixed by this permutation can be computed with procedure fixedcount, which gives A034731.

Index entries for sequences that are permutations of the natural numbers
A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)

Inverse of A057510 and the car/cdr-flipped conjugate of A069775 and also composition of A069770 & A057501, i.e. A057509(n) = A057163(A069775(A057163(n))) = A057501(A069770(n)).

Cycle counts given by A003239. Cf. also A057511.

map(CatalanRankGlobal,map(RotateBottomBranchesL, A014486));
RotateBottomBranchesL := n -> pars2binexp(rotateL(binexp2pars(n)));
rotateL := proc(a) if 0 = nops(a) then (a) else [op(cdr(a)), a[1]]; fi; end;
fixedcount := proc(n) local d,z; z := 0; for d in divisors(n) do z := z+C(d-1); od; RETURN(z); end;

A073202 Array of fix-count sequences for the table A073200.

Original entry on oeis.org

1, 1, 1, 0, 1, 1, 1, 2, 1, 1, 0, 3, 0, 1, 1, 2, 8, 1, 0, 1, 1, 0, 20, 0, 0, 0, 1, 1, 5, 60, 2, 0, 1, 0, 1, 1, 0, 181, 0, 0, 0, 0, 0, 1, 1, 14, 584, 5, 0, 2, 0, 1, 2, 1, 1, 0, 1916, 0, 0, 0, 0, 0, 5, 0, 1, 1, 42, 6476, 14, 0, 5, 0, 0, 14, 1, 2, 1, 1, 0, 22210, 0, 0, 0, 0, 0, 42, 0, 1, 0, 1, 1

Offset: 0

Antti Karttunen, Jun 25 2002

Each row of this table gives the counts of elements fixed by the Catalan bijection (given in the corresponding row of A073200) when it acts on A000108(n) structures encoded in the range [A014137(n-1)..A014138(n-1)] of the sequence A014486/A063171.

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

Cf. also A073201, A073203.
Few EIS-sequences which occur in this table. Only the first known occurrence(s) given (marked with ? if not yet proved/unclear):
Rows 0, 2, 4, etc.: "Aerated Catalan numbers" shifted right and prepended with 1 (Cf. A000108), Row 1: A073190, Rows 3, 5, 261, 2614, 2618, 17517, etc: A019590 but with offset 0 instead of 1 (means that the Catalan bijections like A073269, A073270, A057501, A057505, A057503 and A057161 never fix any Catalan structure of size larger than 1).
Row 6: A036987, Row 7: A000108, Rows 12, 14, 20, ...: A057546, Rows 16, 18: A034731, Row 41: A073268, Row 105: essentially A073267, Row 57, ..., 164: A001405, Row 168: A073192, Row 416: essentially A023359 ?, Row 10435: also A036987.

A069775 Permutation of natural numbers induced by the automorphism gma069775! acting on the parenthesizations encoded by A014486.

Original entry on oeis.org

0, 1, 2, 3, 4, 5, 7, 6, 8, 9, 10, 11, 12, 13, 17, 18, 16, 14, 15, 21, 19, 20, 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, 58, 59, 56, 51, 52, 57, 53, 54, 55, 63, 60, 61, 62, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Inverse of A069776. a(n) = A057163(A057509(A057163(n))) = A069773(A069770(n)). Cf. also A069787, A072797.

Number of cycles: A003239. Number of fixed points: A034731. Max. cycle size: A028310. LCM of cycle sizes: A003418. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A069776 Permutation of natural numbers induced by the automorphism gma069776! acting on the parenthesizations encoded by A014486.

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, 21, 19, 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, 57, 58, 59, 53, 56, 51, 52, 61, 62, 63, 60, 64, 65, 66, 67, 68, 69, 70, 71

Offset: 0

Antti Karttunen, Apr 16 2002

nonn

A. Karttunen, Gatomorphisms (Includes the complete Scheme program for computing this sequence)
Index entries for sequences that are permutations of the natural numbers

Inverse of A069775. a(n) = A057163(A057510(A057163(n))) = A069770(A069774(n)). Cf. also A069787, A072797.

Number of cycles: A003239. Number of fixed points: A034731. Max. cycle size: A028310. LCM of cycle sizes: A003418. (In range [A014137(n-1)..A014138(n-1)] of this permutation, possibly shifted one term left or right).

A349563 Dirichlet convolution of right-shifted Catalan numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Original entry on oeis.org

1, -1, -2, -1, -2, 18, 68, 311, 1182, 4370, 15772, 56754, 203916, 734636, 2658096, 9661591, 35292134, 129511602, 477376556, 1766730706, 6563071700, 24464139348, 91478369336, 343051112482, 1289887370140, 4861912443284, 18367285959072, 69533415236716, 263747683314904, 1002241674463968, 3814985428350480, 14544633872450487

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution with A034729 gives A034731.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A000108, A011782, A349452, A349564 (Dirichlet inverse).

Cf. also A034729, A034731, A349565, A349567, A349569.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * 2^(n/# - 1) &, # < n &]; a[n_] := DivisorSum[n, CatalanNumber[# - 1] * s[n/#] &]; Array[a, 32] (* Amiram Eldar, Nov 22 2021 *)

A000108(n) = (binomial(2*n, n)/(n+1));
A011782(n) = (2^(n-1));
memoA349452 = Map();
A349452(n) = if(1==n,1,my(v); if(mapisdefined(memoA349452,n,&v), v, v = -sumdiv(n,d,if(dA011782(n/d)*A349452(d),0)); mapput(memoA349452,n,v); (v)));
A349563(n) = sumdiv(n,d,A000108(d-1)*A349452(n/d));

a(n) = Sum_{d|n} A000108(d-1) * A349452(n/d).

A349564 Dirichlet convolution of A011782 [2^(n-1)] with A349450 [Dirichlet inverse of right-shifted Catalan numbers].

Original entry on oeis.org

1, 1, 2, 2, 2, -14, -68, -308, -1178, -4366, -15772, -56780, -203916, -734772, -2658088, -9662208, -35292134, -129514026, -477376556, -1766739436, -6563071972, -24464170892, -91478369336, -343051227304, -1289887370136, -4861912851116, -18367285963792, -69533416706328, -263747683314904, -1002241679797688

Offset: 1

Antti Karttunen, Nov 22 2021

sign

Dirichlet convolution with A034731 gives A034729.

Antti Karttunen, Table of n, a(n) for n = 1..1001

Cf. A011782, A349450.
Cf. A000108, A011782, A349452, A349563 (Dirichlet inverse).
Cf. also A034729, A034731, A349566, A349568.

s[1] = 1; s[n_] := s[n] = -DivisorSum[n, s[#] * CatalanNumber[n/# - 1] &, # < n &]; a[n_] := DivisorSum[n, 2^(# - 1) * s[n/#] &]; Array[a, 30] (* Amiram Eldar, Nov 22 2021 *)

A000108(n) = (binomial(2*n, n)/(n+1));
memoA349450 = Map();
A349450(n) = if(1==n,1,my(v); if(mapisdefined(memoA349450,n,&v), v, v = -sumdiv(n,d,if(dA000108((n/d)-1)*A349450(d),0)); mapput(memoA349450,n,v); (v)));
A349564(n) = sumdiv(n,d,2^(d-1)*A349450(n/d));

a(n) = Sum_{d|n} 2^(d-1) * A349450(n/d).

A066768 Sum_{d|n} binomial(2*d-2,d-1).

Original entry on oeis.org

1, 3, 7, 23, 71, 261, 925, 3455, 12877, 48693, 184757, 705713, 2704157, 10401527, 40116677, 155120975, 601080391, 2333619351, 9075135301, 35345312513, 137846529751, 538258059199, 2104098963721, 8233431436745, 32247603683171

Offset: 1

Vladeta Jovovic, Jan 17 2002

nonn

Cf. A034731, A052854.

Cf. A051731, A000984.

Table[Sum[Binomial[2*d-2,d-1], {d, Divisors[n]}], {n,1,30}] (* Vaclav Kotesovec, Jun 08 2019 *)

a(n)=if(n<1,0,sumdiv(n,d,binomial(2*d-2,d-1)))

a(n)=polcoeff(sum(m=1,n,x^m/sqrt(1-4*x^m+x*O(x^n))),n) /* Paul D. Hanna */

G.f.: Sum_{n>=1} x^n/sqrt(1-4*x^n). [From Paul D. Hanna, Aug 23 2011]
Logarithmic derivative of A052854, the number of unordered forests on n nodes.
Equals A051731 * A000984, i.e. the inverse Mobius transform of A000984. - Gary W. Adamson, Nov 09 2007
a(n) ~ 4^(n-1) / sqrt(Pi*n). - Vaclav Kotesovec, Jun 08 2019

cp's OEIS Frontend

A057546 Number of Catalan objects of size n fixed by Catalan Automorphism A057511/A057512 (deep rotation of general parenthesizations/plane trees).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A057509 Permutation of natural numbers: rotations of the bottom branches of the rooted plane trees encoded by A014486.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

A073202 Array of fix-count sequences for the table A073200.

Views

Author

Keywords

Comments

Links

Crossrefs

A069775 Permutation of natural numbers induced by the automorphism gma069775! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A069776 Permutation of natural numbers induced by the automorphism gma069776! acting on the parenthesizations encoded by A014486.

Views

Author

Keywords

Links

Crossrefs

A349563 Dirichlet convolution of right-shifted Catalan numbers with A349452 (Dirichlet inverse of A011782, 2^(n-1)).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A349564 Dirichlet convolution of A011782 [2^(n-1)] with A349450 [Dirichlet inverse of right-shifted Catalan numbers].

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A066768 Sum_{d|n} binomial(2*d-2,d-1).

Views

Author

Keywords

Crossrefs

Programs

Mathematica

PARI

PARI

Formula