A295634 -id:A295634 - 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]))

A295633 Triangle read by rows: T(n,k) = number of nonequivalent dissections of an n-gon into k polygons by nonintersecting diagonals up to rotation.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 2, 4, 4, 1, 2, 8, 12, 6, 1, 3, 16, 40, 43, 19, 1, 3, 25, 93, 165, 143, 49, 1, 4, 40, 197, 505, 712, 504, 150, 1, 4, 56, 364, 1274, 2548, 2912, 1768, 442, 1, 5, 80, 646, 2878, 7672, 12400, 11976, 6310, 1424, 1, 5, 105, 1050, 5880, 19992, 42840, 58140, 48450, 22610, 4522

Offset: 3

Andrew Howroyd, Nov 24 2017

			Triangle begins: (n >= 3, k >= 1)
1;
1, 1;
1, 1,  1;
1, 2,  4,   4;
1, 2,  8,  12,    6;
1, 3, 16,  40,   43,   19;
1, 3, 25,  93,  165,  143,   49;
1, 4, 40, 197,  505,  712,  504,  150;
1, 4, 56, 364, 1274, 2548, 2912, 1768, 442;
...

Andrew Howroyd, Table of n, a(n) for n = 3..1277

Row sums are A003455.
Column k=3 is A003451.
Diagonals include A001683, A220881, A003445, A220882.
Cf. A295224, A295495, A295634.

\\ See A295495 for DissectionsModCyclic()
T=DissectionsModCyclic(apply(i->y, [1..12]));
for(n=3, #T, for(k=1, n-2, print1(polcoeff(T[n], k), ", ")); print)

A003450 Number of nonequivalent dissections of an n-gon into n-4 polygons by nonintersecting diagonals up to rotation and reflection.

Original entry on oeis.org

1, 2, 6, 24, 89, 371, 1478, 6044, 24302, 98000, 392528, 1570490, 6264309, 24954223, 99253318, 394409402, 1565986466, 6214173156, 24647935156, 97732340680, 387428854374, 1535588541762, 6085702368796, 24116801236744, 95569050564444, 378718095630676

Offset: 5

N. J. A. Sloane

nonn

In other words, the number of (n - 5)-dissections of an n-gon modulo the dihedral action.
Equivalently, the number of two-dimensional faces of the (n-3)-dimensional associahedron modulo the dihedral action.
The dissection will always be composed of either 1 pentagon and n-5 triangles or 2 quadrilaterals and n-6 triangles. - Andrew Howroyd, Nov 24 2017

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 5..200
D. Bowman and A. Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv:1209.6270 [math.CO], 2012.
P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.

A diagonal of A295634.
Cf. A003449, A295419.
Cf. A003444, A003445, A220881.

C:=n->binomial(2*n,n)/(n+1);
T32:=proc(n) local t1; global C;
if n mod 2 = 0 then
t1 :=  (n-3)^2*(n-4)*C(n-2)/(8*n*(2*n-5));
if n mod 5 = 0 then t1:=t1+(2/5)*C(n/5-1) fi;
if n mod 2 = 0 then t1:=t1+((3*(n-4)*(n-1))/(16*(n-3)))*C(n/2-1) fi;
else
t1 :=  (n-3)^2*(n-4)*C(n-2)/(8*n*(2*n-5));
if n mod 5 = 0 then t1:=t1+(2/5)*C(n/5-1) fi;
if n mod 2 = 1 then t1:=t1+((n^2-2*n-11)/(8*(n-4)))*C((n-3)/2) fi;
fi;
t1; end;
[seq(T32(n),n=5..40)];

c = CatalanNumber;
T32[n_] := Module[{t1}, If[EvenQ[n], t1 = (n-3)^2*(n-4)*c[n-2]/(8*n*(2*n - 5)); If[Mod[n, 5] == 0, t1 = t1 + (2/5)*c[n/5-1]]; If[EvenQ[n], t1 = t1 + ((3*(n-4)*(n-1))/(16*(n-3)))*c[n/2-1]], t1 = (n-3)^2*(n-4)*c[n-2]/(8*n *(2*n - 5)); If[Mod[n, 5] == 0, t1 = t1 + (2/5) * c[n/5-1]]; If[OddQ[n], t1 = t1 + ((n^2 - 2*n - 11)/(8*(n-4)))*c[(n-3)/2]]]; t1];
Table[T32[n], {n, 5, 40}] (* Jean-François Alcover, Dec 11 2017, translated from Maple *)

\\ See A295419 for DissectionsModDihedral()
{ my(v=DissectionsModDihedral(apply(i->if(i>=3&&i<=5, y^(i-3) + O(y^3)), [1..30]))); apply(p->polcoeff(p, 2), v[5..#v]) } \\ Andrew Howroyd, Nov 24 2017

See Maple program.

Entry revised (following Bowman and Regev) by N. J. A. Sloane, Dec 28 2012

Name clarified by Andrew Howroyd, Nov 24 2017

A003453 Number of nonequivalent dissections of an n-gon into 3 polygons by nonintersecting diagonals up to rotation and reflection.

Original entry on oeis.org

1, 3, 6, 11, 17, 26, 36, 50, 65, 85, 106, 133, 161, 196, 232, 276, 321, 375, 430, 495, 561, 638, 716, 806, 897, 1001, 1106, 1225, 1345, 1480, 1616, 1768, 1921, 2091, 2262, 2451, 2641, 2850, 3060, 3290, 3521, 3773, 4026

Offset: 5

N. J. A. Sloane, Simon Plouffe

In other words, the number of 2-dissections of an n-gon modulo the dihedral action.
John W. Layman observes that this appears to be the alternating sum transform (PSumSIGN) of A005744.
Row 2 of the convolution array A213847. - Clark Kimberling, Jul 05 2012
Number of nonisomorphic outer planar graphs of order n >= 3 and size n+2. - Christian Barrientos and Sarah Minion, Feb 27 2018

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n=5..1000
Douglas Bowman and Alon Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv preprint arXiv:1209.6270 [math.CO], 2012. See Theorem 5(2).
P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
Petr Lisonek, Combinatorial families enumerated by quasi-polynomials, Journal of Combinatorial Theory, Series A, Volume 114, Issue 4, May 2007, Pages 619-630.
Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.
N. J. A. Sloane, Transforms
Index entries for linear recurrences with constant coefficients, signature (2,1,-4,1,2,-1).

Column 3 of A295634.

Cf. A005744, A213847, A295419.

T52:= proc(n)
if n mod 2 = 0 then (n-4)*(n-2)*(n+3)/24;
else (n-3)*(n^2-13)/24; fi end;
[seq(T52(n),n=5..80)]; # N. J. A. Sloane, Dec 28 2012

nd[n_]:=If[EvenQ[n],(n-4)(n-2) (n+3)/24,(n-3) (n^2-13)/24]; Array[nd,50,5] (* or *) LinearRecurrence[{2,1,-4,1,2,-1},{1,3,6,11,17,26},50] (* Harvey P. Dale, Jan 28 2013 *)

\\ See A295419 for DissectionsModDihedral()
{ my(v=DissectionsModDihedral(apply(i->y + O(y^4), [1..40]))); apply(p->polcoeff(p, 3), v[5..#v]) } \\ Andrew Howroyd, Nov 24 2017

G.f.: (1+x-x^2) / ((1-x)^4*(1+x)^2).
See also the Maple code.
a(5)=1, a(6)=3, a(7)=6, a(8)=11, a(9)=17, a(10)=26, a(n) = 2*a(n-1) + a(n-2) - 4*a(n-3) + a(n-4) + 2*a(n-5) - a (n-6). - Harvey P. Dale, Jan 28 2013
a(n) = (2*n^3-6*n^2-23*n+63+3*(n-5)*(-1)^n)/48, for n>=5. - Luce ETIENNE, Apr 07 2015
a(n) = (1/2) * Sum_{i=1..n-4} floor((i+1)*(n-i-2)/2). - Wesley Ivan Hurt, May 07 2016

Entry revised (following Bowman and Regev) by N. J. A. Sloane, Dec 28 2012

Name clarified by Andrew Howroyd, Nov 24 2017

A003449 Number of nonequivalent dissections of an n-gon into n-3 polygons by nonintersecting diagonals up to rotation and reflection.

Original entry on oeis.org

1, 1, 3, 7, 24, 74, 259, 891, 3176, 11326, 40942, 148646, 543515, 1996212, 7367075, 27294355, 101501266, 378701686, 1417263770, 5318762098, 20011847548, 75473144396, 285267393358, 1080432637662, 4099856060808, 15585106611244, 59343290815356

Offset: 4

N. J. A. Sloane

nonn

In other words, the number of almost-triangulations of an n-gon modulo the dihedral action.
Equivalently, the number of edges of the (n-3)-dimensional associahedron modulo the dihedral action.
The dissection will always be composed of one quadrilateral and n-4 triangles. - Andrew Howroyd, Nov 24 2017
See Theorem 30 of Bowman and Regev (although there appears to be a typo in the formula - see Maple code below). - N. J. A. Sloane, Dec 28 2012

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Andrew Howroyd, Table of n, a(n) for n = 4..200
D. Bowman and A. Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv:1209.6270 [math.CO], 2012.
P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.

A diagonal of A295634.

Cf. A003450, A295419.

C:=n->binomial(2*n,n)/(n+1);
T30:=proc(n) local t1; global C;
if n mod 2 = 0 then
t1:=(1/4-(3/(4*n)))*C(n-2) + (3/8)*C(n/2-1) + (1-3/n)*C(n/2-2);
if n mod 4 = 0 then t1:=t1+C(n/4-1)/4 fi;
else
t1:=(1/4-(3/(4*n)))*C(n-2) + (1/2)*C((n-3)/2);
fi;
t1; end;
[seq(T30(n),n=4..40)]; # N. J. A. Sloane, Dec 28 2012

c = CatalanNumber;
T30[n_] := Module[{t1}, If[EvenQ[n], t1 = (1/4 - (3/(4*n)))*c[n - 2] + (3/8)*c[n/2 - 1] + (1 - 3/n)*c[n/2 - 2]; If[Mod[n, 4] == 0, t1 = t1 + c[n/4 - 1]/4], t1 = (1/4 - (3/(4*n)))*c[n-2] + (1/2)*c[(n-3)/2]]; t1];
Table[T30[n], {n, 4, 40}] (* Jean-François Alcover, Dec 14 2017, after N. J. A. Sloane *)

\\ See A295419 for DissectionsModDihedral()
{ my(v=DissectionsModDihedral(apply(i->if(i>=3&&i<=4, y^(i-3) + O(y^2)), [1..25]))); apply(p->polcoeff(p, 1), v[4..#v]) } \\ Andrew Howroyd, Nov 24 2017

Entry revised (following Bowman and Regev) by N. J. A. Sloane, Dec 28 2012

Name clarified by Andrew Howroyd, Nov 24 2017

A380362 Triangle read by rows: T(n,k) is the number of Halin graphs on n unlabeled nodes with circuit rank k, 3 <= k <= n-1.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 0, 3, 2, 1, 0, 0, 0, 3, 6, 3, 1, 0, 0, 0, 0, 7, 11, 3, 1, 0, 0, 0, 0, 4, 24, 17, 4, 1, 0, 0, 0, 0, 0, 24, 51, 26, 4, 1, 0, 0, 0, 0, 0, 12, 89, 109, 36, 5, 1, 0, 0, 0, 0, 0, 0, 74, 265, 194, 50, 5, 1, 0, 0, 0, 0, 0, 0, 27, 371, 660, 345, 65, 6, 1

Offset: 4

Andrew Howroyd, Jan 25 2025

The circuit rank is equal to the number of leaves on the tree before it is extended into a Halin graph by joining up the leaves.
The main diagonal of the graph corresponds with the wheel graphs which have the greatest circuit rank of all Halin graphs.
T(n,k) is also the number of nonequivalent dissections of a k-gon into n-k polygons by nonintersecting diagonals up to rotations and reflections.

			Triangle begins:
  n\k| 3  4  5  6  7   8   9   10  11  12  13
-----+----------------------------------------
   4 | 1;
   5 | 0, 1;
   6 | 0, 1, 1;
   7 | 0, 0, 1, 1;
   8 | 0, 0, 1, 2, 1;
   9 | 0, 0, 0, 3, 2,  1;
  10 | 0, 0, 0, 3, 6,  3,  1;
  11 | 0, 0, 0, 0, 7, 11,  3,   1;
  12 | 0, 0, 0, 0, 4, 24, 17,   4,  1;
  13 | 0, 0, 0, 0, 0, 24, 51,  26,  4,  1;
  14 | 0, 0, 0, 0, 0, 12, 89, 109, 36,  5,  1;
   ...

Andrew Howroyd, Table of n, a(n) for n = 4..1278 (first 50 rows)
Andrew Howroyd, Formulas and PARI Program, Jan 2025.
Eric Weisstein's World of Mathematics, Halin Graph.
Wikipedia, Circuit rank.
Wikipedia, Halin graph.

Row sums are A346779.
Column sums are A001004.
Main diagonal is A000012.
Central coefficients are A000207.
Cf. A295634, A380361.

\\ See PARI Link for program code.
{ my(T=A380361rows(12)); for(i=1, #T, print(T[i])) }

T(n,k) = A295634(k, n-k).

A346779 Number of Halin graphs on n unlabeled nodes.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 4, 6, 13, 22, 50, 106, 252, 589, 1475, 3669, 9435, 24345, 63837, 168234, 447562, 1196390, 3218221, 8694411, 23598318, 64292975, 175820236, 482391019, 1327680919, 3664644419, 10142533143, 28141900501, 78269260312, 218170198957, 609414024190

Offset: 1

Eric W. Weisstein, Aug 03 2021

nonn

			a(4) = 1 (K_4)
a(5) = 1 (W_5)
a(6) = 2 (3-prism graph, W_6)
a(7) = 2 (W_7 and one other)
a(8) = 4 (W_8 and 3 others)

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Peter J. Taylor, Python program
Eric Weisstein's World of Mathematics, Halin Graph.
Wikipedia, Halin graph.

Row sums of A380362.
Antidiagonal sums of A295634.
Cf. A380360.

A346779seq(36) \\ See PARI Link in A380362 for program code. - Andrew Howroyd, Jan 26 2025

Python
```
# See Taylor link
```

a(13) from Eric W. Weisstein, Aug 16 2021
a(14) from Eric W. Weisstein, Sep 29 2021
a(15)-a(24) from Peter J. Taylor, May 20 2023
a(25) onwards from Andrew Howroyd, Jan 25 2025

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

A295633 Triangle read by rows: T(n,k) = number of nonequivalent dissections of an n-gon into k polygons by nonintersecting diagonals up to rotation.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

A003450 Number of nonequivalent dissections of an n-gon into n-4 polygons by nonintersecting diagonals up to rotation and reflection.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003453 Number of nonequivalent dissections of an n-gon into 3 polygons by nonintersecting diagonals up to rotation and reflection.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A003449 Number of nonequivalent dissections of an n-gon into n-3 polygons by nonintersecting diagonals up to rotation and reflection.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A380362 Triangle read by rows: T(n,k) is the number of Halin graphs on n unlabeled nodes with circuit rank k, 3 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A346779 Number of Halin graphs on n unlabeled nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs