A295419 - OEIS

%I #16 Sep 25 2019 05:57:37

%S 1,1,2,4,8,23,64,222,752,2805,10475,40614,158994,633456,2548241,

%T 10362685,42485242,175557329,730314350,3056971164,12867007761,

%U 54434131848,231354091945,987496927875,4231561861914,18198894300129,78533356685275,339958801585826

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

%C 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.

%H Andrew Howroyd, <a href="/A295419/b295419.txt">Table of n, a(n) for n = 3..200</a>

%H E. Krasko, A. Omelchenko, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p17">Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees</a>, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.

%t 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]];

%t DissectionsModDihedral[Boole[PrimeQ[#]]& /@ Range[1, 31]] (* _Jean-François Alcover_, Sep 25 2019, after _Andrew Howroyd_ *)

%o (PARI) \\ number of dissections into parts defined by set.

%o DissectionsModDihedral(v)={my(n=#v);

%o my(q=vector(n)); q[1]=serreverse(x-sum(i=3,#v,x^i*v[i])/x + O(x*x^n));

%o for(i=2, n, q[i]=q[i-1]*q[1]);

%o my(vars=variables(q[1]));

%o my(u(m, r)=substvec(q[r]+O(x^(n\m+1)), vars, apply(t->t^m, vars)));

%o 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)));

%o 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);

%o vector(n,i,polcoeff(p,i))}

%o DissectionsModDihedral(apply(v->isprime(v), [1..25]))

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

%K nonn

%O 3,3

%A _Andrew Howroyd_, Nov 22 2017