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

Author

Andrew Howroyd, Nov 22 2017

Keywords

• nonn

Comments

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.

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. A001004, A290571, A290646, A290722, A290816, A295260, A295634.

Programs

Mathematica

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

PARI

\\ 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]))