A290646 -id:A290646 - cp's OEIS frontend

A295419 Number of dissections of an n-gon by nonintersecting diagonals into polygons with a prime number of sides counted up to rotations and reflections.

1, 1, 2, 4, 8, 23, 64, 222, 752, 2805, 10475, 40614, 158994, 633456, 2548241, 10362685, 42485242, 175557329, 730314350, 3056971164, 12867007761, 54434131848, 231354091945, 987496927875, 4231561861914, 18198894300129, 78533356685275, 339958801585826

Offset: 3

Andrew Howroyd, Nov 22 2017

nonn

a(n) first differs from A290816(n) at n=9 since this sequence does not allow the trivial dissection of a nonagon into a single nonagon.

Andrew Howroyd, Table of n, a(n) for n = 3..200
E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.

Cf. A001004, A290571, A290646, A290722, A290816, A295260, A295634.

DissectionsModDihedral[v_] := Module[{n = Length[v], q, vars, u, R, Q, T, p}, q = Table[0, {n}]; q[[1]] = InverseSeries[x - Sum[x^i v[[i]], {i, 3, Length[v]}]/x + O[x]^(n+1)]; For[i = 2, i <= n, i++, q[[i]] = q[[i-1]] q[[1]]]; vars = Variables[q[[1]]]; u[m_, r_] := Normal[(q[[r]] + O[x]^(Quotient[n, m]+1))] /. Thread[vars -> vars^m]; R = Sum[v[[2i+1]] u[2, i], {i, 1, (Length[v]-1)/2 // Floor}]; Q = Sum[v[[2i]] u[2, i-1], {i, 2, Length[v]/2 // Floor}]; T = Sum[v[[i]] Sum[EulerPhi[d] u[d, i/d], {d, Divisors[i]}]/i, {i, 3, Length[v]}]; p = O[x]^n - x^2 + (x u[1, 1] + u[2, 1] + (Q u[2, 1] - u[1, 2] + (x+R)^2/(1-Q))/2 + T)/2; Drop[ CoefficientList[p, x], 3]];
DissectionsModDihedral[Boole[PrimeQ[#]]& /@ Range[1, 31]] (* Jean-François Alcover, Sep 25 2019, after Andrew Howroyd *)

\\ number of dissections into parts defined by set.
DissectionsModDihedral(v)={my(n=#v);
my(q=vector(n)); q[1]=serreverse(x-sum(i=3,#v,x^i*v[i])/x + O(x*x^n));
for(i=2, n, q[i]=q[i-1]*q[1]);
my(vars=variables(q[1]));
my(u(m, r)=substvec(q[r]+O(x^(n\m+1)), vars, apply(t->t^m, vars)));
my(R=sum(i=1, (#v-1)\2, v[2*i+1]*u(2,i)), Q=sum(i=2, #v\2, v[2*i]*u(2,i-1)), T=sum(i=3, #v, my(c=v[i]); if(c, c*sumdiv(i, d, eulerphi(d)*u(d,i/d))/i)));
my(p=O(x*x^n) - x^2 + (x*u(1,1) + u(2,1) + (Q*u(2,1) - u(1,2) + (x+R)^2/(1-Q))/2 + T)/2);
vector(n,i,polcoeff(p,i))}
DissectionsModDihedral(apply(v->isprime(v), [1..25]))

A135517 a(n) = 2^(A091090(n)-1).

Original entry on oeis.org

1, 1, 1, 2, 1, 2, 1, 4, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 16, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 32, 1, 2, 1, 4, 1, 2, 1, 8

Offset: 0

N. J. A. Sloane, based on a message from Guy Steele and Don Knuth, Mar 01 2008

Also, a(n) = denominator(Euler(n, x) - Euler(n, 1)). - Observation from Peter Luschny, Aug 08 2017, proof from Vladimir Shevelev, Aug 13 2017

Also, a(n) = denominator(Euler(n,x) + Euler(n,0)). - Vladimir Shevelev, Aug 09 2017

Robert Israel, Table of n, a(n) for n = 0..10000
Vladimir Shevelev, Is A290646 = A135517?, Posting to Sequence Fans Mailing List, Aug 13 2017
Vladimir Shevelev, On a Luschny question, arXiv:1708.08096 [math.NT], 2017.

This is Guy Steele's sequence GS(2, 5) (see A135416).

Cf. A091090.

GS(2,5,200); # see A135416.
a := n -> `if`(n=1 or n mod 2 = 0, 1, 2*a(iquo(n,2))):
seq(a(n), n=0..103); # Peter Luschny, Aug 09 2017

b[n_] := b[n] = Which[n==0, 1, n==1, 1, EvenQ[n], 1, True, b[(n-1)/2] + 1]; a[n_] := 2^(b[n+1]-1); Array[a,103,0] (* Jean-François Alcover, Aug 12 2017 *)

a(n)=my(m=valuation(n+1,2)); 2^if(n>>m, m, m-1) \\ Charles R Greathouse IV, Aug 15 2017

def A135517(n): return (1<<(~(n+1)&n).bit_length()-(not n&(n+1))) if n else 1 # Chai Wah Wu, Sep 18 2024

For n >= 1, a(n) = 2^max_{odd k=1..n} (A007814(k+1) - t(n,k) - delta(n,k)), where delta(n,k) is the Kronecker symbol: delta(i,j) is 1 if i=j and 0 otherwise, and t(n,k) is the number of carries which appear in the addition of k and n-k in base 2. This allows us to answer in the affirmative the author's question (for a proof see Shevelev's link and its continuations). - Vladimir Shevelev, Aug 15 2017

Entry revised by N. J. A. Sloane, Aug 31 2017

A290571 Number of dissections of an n-gon into 3- and 5-gons counted up to rotations and reflections.

Original entry on oeis.org

1, 1, 2, 4, 7, 22, 60, 208, 695, 2566, 9451, 36158, 139574, 548347, 2174801, 8719651, 35244472, 143581782, 588858667, 2430036786, 10083626092, 42055927173, 176217259551, 741517642476, 3132564196880, 13281805256068, 56503895845238, 241135999611542

Offset: 3

Evgeniy Krasko, Sep 03 2017

nonn

			For a(5) = 2 the dissections of a pentagon are: a dissection into 3 triangles; a dissection into one pentagon.

Andrew Howroyd, Table of n, a(n) for n = 3..200
E. Krasko, A. Omelchenko, Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.

Cf. A001004, A290646, A295260.

\\ See A295419 for DissectionsModDihedral().
DissectionsModDihedral(apply(v->v==3||v==5, [1..25])) \\ Andrew Howroyd, Nov 22 2017

Terms a(16) and beyond from Andrew Howroyd, Nov 22 2017

cp's OEIS Frontend

A295419 Number of dissections of an n-gon by nonintersecting diagonals into polygons with a prime number of sides counted up to rotations and reflections.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A135517 a(n) = 2^(A091090(n)-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A290571 Number of dissections of an n-gon into 3- and 5-gons counted up to rotations and reflections.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions