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

1, 1, 2, 5, 11, 36, 114, 410, 1458, 5488, 20786, 80770, 317378, 1265139, 5094139, 20718347, 84961256, 351086326, 1460591637, 6113826319, 25733864299, 108867782794, 462707558813, 1974991841442, 8463121111860, 36397780088126, 157066702354947, 679917566925030

Offset: 3

Author

Andrew Howroyd, Nov 22 2017

Keywords

• nonn

Links

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

Crossrefs

Cf. A003455, A295224, A295419.

Programs

Mathematica

DissectionsModCyclic[v_] :=
Module[{n = Length[v], q, vars, u, 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]; p = O[x]^n + x u[1, 1] - x^2 + (u[2, 1] - u[1, 2])/2 + Sum[v[[i]] Sum[EulerPhi[d] u[d, i/d]/i, {d, Divisors[i]}], {i, 3, Length[v]}]; Drop[CoefficientList[p, x], 3]];
DissectionsModCyclic[Boole[PrimeQ[#]]& /@ Range[1, 31]] (* Jean-François Alcover, Sep 26 2019, after Andrew Howroyd *)

PARI

\\ number of dissections into parts defined by set.
DissectionsModCyclic(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(p=O(x*x^n) + x*u(1,1) - x^2 + (u(2,1)-u(1,2))/2 + sum(i=3, #v, my(c=v[i]); if(c,c*sumdiv(i, d, eulerphi(d)*u(d,i/d))/i)));
vector(n, i, polcoeff(p, i))}
DissectionsModCyclic(apply(i->isprime(i), [1..30]))