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
Keywords
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.
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]))
Comments