A295633 -id:A295633 - cp's OEIS frontend

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

1, 1, 1, 1, 1, 1, 1, 2, 3, 3, 1, 2, 6, 7, 4, 1, 3, 11, 24, 24, 12, 1, 3, 17, 51, 89, 74, 27, 1, 4, 26, 109, 265, 371, 259, 82, 1, 4, 36, 194, 660, 1291, 1478, 891, 228, 1, 5, 50, 345, 1477, 3891, 6249, 6044, 3176, 733, 1, 5, 65, 550, 3000, 10061, 21524, 29133, 24302, 11326, 2282

Offset: 3

Andrew Howroyd, Nov 24 2017

			Triangle begins: (n >= 3, k >= 1)
1;
1, 1;
1, 1,  1;
1, 2,  3,   3;
1, 2,  6,   7,   4;
1, 3, 11,  24,  24,   12;
1, 3, 17,  51,  89,   74,   27;
1, 4, 26, 109, 265,  371,  259,  82;
1, 4, 36, 194, 660, 1291, 1478, 891, 228;
...

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

Row sums are A001004.
Column k=3 is A003453.
Diagonals include A000207, A003449, A003450.
Cf. A295260, A295419, A295633.

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

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

Original entry on oeis.org

1, 2, 8, 40, 165, 712, 2912, 11976, 48450, 195580, 784504, 3139396, 12526605, 49902440, 198499200, 788795924, 3131945190, 12428258796, 49295766000, 195464345440, 774857314042, 3071175790232, 12171403236288, 48233597481200, 191138095393700, 757436171945952

Offset: 5

N. J. A. Sloane

nonn

In other words, the number of (n-5)-dissections of an n-gon modulo the cyclic action.
Equivalently, the number of two-dimensional faces of the (n-3)-dimensional associahedron modulo the cyclic 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).

T. D. Noe, 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 A295633.
Cf. A003444, A003450, A220881.
Cf. A003443, A003448, A003450.

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

Table[t1 = (n - 3)^2*(n - 4)*CatalanNumber[n - 2]/(4*n*(2*n - 5)); If[Mod[n, 5] == 0, t1 = t1 + (4/5)*CatalanNumber[n/5 - 1]]; If[Mod[n, 2] == 0, t1 = t1 + (n - 4)*CatalanNumber[n/2 - 1]/8]; t1, {n, 5, 20}] (* T. D. Noe, Jan 03 2013 *)

\\ See A295495 for DissectionsModCyclic()
{ my(v=DissectionsModCyclic(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 25 2017

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

Original entry on oeis.org

1, 1, 4, 12, 43, 143, 504, 1768, 6310, 22610, 81752, 297160, 1086601, 3991995, 14732720, 54587280, 202997670, 757398510, 2834510744, 10637507400, 40023636310, 150946230006, 570534578704, 2160865067312, 8199711378716, 31170212479588, 118686578956272

Offset: 4

N. J. A. Sloane, Dec 28 2012

nonn

This is almost identical to A003444, but has a different offset and a more precise definition.
In other words, the number of almost-triangulations of an n-gon modulo the cyclic action.
Equivalently, the number of edges of the (n-3)-dimensional associahedron modulo the cyclic action.
The dissection will always be composed of one quadrilateral and n-4 triangles. - Andrew Howroyd, Nov 25 2017
Also number of necklaces of 2 colors with 2n-4 beads and n black ones. - Wouter Meeussen, Aug 03 2002

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

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 A295633.
Cf. A003444, A003445.
Cf. A003442, A003447, A003449.

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

c[n_] := Binomial[2*n, n]/(n+1);
T2[n_] := Module[{t1}, t1 = (n-3)*c[n-2]/(2*n); If[Mod[n, 4] == 0, t1 = t1 + c[n/4-1]/2]; If[Mod[n, 2] == 0, t1 = t1 + c[n/2-1]/4]; t1];
Table[T2[n], {n, 4, 40}] (* Jean-François Alcover, Nov 23 2017, translated from Maple *)
a[n_] := Sum[EulerPhi[d]*Binomial[(2n-4)/d, n/d], {d, Divisors[GCD[2n-4, n] ]}]/(2n-4);
Array[a, 30, 4] (* Jean-François Alcover, Dec 02 2017, after Andrew Howroyd *)

a(n) = if(n>=4, sumdiv(gcd(2*n-4, n), d, eulerphi(d)*binomial((2*n-4)/d, n/d))/(2*n-4)) \\ Andrew Howroyd, Nov 25 2017

a(n) = (1/(2n-4)) Sum_{d |(2n-4, n)} phi(d)*binomial((2n-4)/d, n/d) for n >= 4. - Wouter Meeussen, Aug 03 2002

Name clarified by Andrew Howroyd, Nov 25 2017

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

Original entry on oeis.org

1, 4, 8, 16, 25, 40, 56, 80, 105, 140, 176, 224, 273, 336, 400, 480, 561, 660, 760, 880, 1001, 1144, 1288, 1456, 1625, 1820, 2016, 2240, 2465, 2720, 2976, 3264, 3553, 3876, 4200, 4560, 4921, 5320, 5720, 6160, 6601, 7084, 7568, 8096, 8625, 9200, 9776, 10400

Offset: 5

N. J. A. Sloane

nonn

In other words, the number of 2-dissections of an n-gon modulo the cyclic action.

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

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.
Index entries for linear recurrences with constant coefficients, signature (2, 1, -4, 1, 2, -1).

Column 3 of A295633.

Cf. A003453, A006584, A027656.

[(n-4)*(2*n^2-4*n-3*(1-(-1)^n))/24: n in [5..60]]; // Vincenzo Librandi, Apr 05 2015

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

Table[((n - 4) (2 n^2 - 4 n - 3 (1 - (-1)^n)) / 24), {n, 5, 60}] (* Vincenzo Librandi, Apr 05 2015 *)
CoefficientList[Series[(1+2*x-x^2)/((1-x)^4*(1+x)^2),{x,0,20}],x] (* Vaclav Kotesovec, Apr 05 2015 *)

Vec((1 + 2*x - x^2 ) / ((1 - x)^4*(1 + x)^2) + O(x^50)) \\ Michel Marcus, Apr 04 2015

\\ See A295495 for DissectionsModCyclic()
{ my(v=DissectionsModCyclic(apply(i->y, [1..30]))); apply(p->polcoeff(p, 3), v[5..#v]) } \\ Andrew Howroyd, Nov 24 2017

G.f.: x^5 * (1 + 2*x - x^2 ) / ((1 - x)^4*(1 + x)^2).
See also the Maple code for an explicit formula.
a(n) = A006584(n+3) - A027656(n). - Yosu Yurramendi, Aug 07 2008
a(n) = (n-4)*(2*n^2-4*n-3*(1-(-1)^n))/24, for n>=5. - Luce ETIENNE, Apr 04 2015

Entry revised (following Bowman and Regev) by N. J. A. Sloane, Dec 28 2012
First formula adapted to offset by Vaclav Kotesovec, Apr 05 2015
Name clarified by Andrew Howroyd, Nov 25 2017

A380360 Number of embeddings on the sphere of Halin graphs on n unlabeled nodes up to orientation-preserving homeomorphisms.

Original entry on oeis.org

0, 0, 0, 1, 1, 2, 2, 4, 7, 16, 32, 76, 181, 443, 1098, 2793, 7127, 18458, 48128, 126580, 334955, 892187, 2388674, 6428489, 17377599, 47174939, 128555088, 351580903, 964696719, 2655197386, 7329051870, 20284610084, 56283140111, 156537249660, 436338547904, 1218824493990, 3411297202411

Offset: 1

Andrew Howroyd, Jan 25 2025

nonn

Halin graphs are planar and 3-connected and can be embedding in the sphere in essentially one way up to mirror symmetry. This sequence counts each graph as either 1 or 2 depending on if it is mirror symmetric.

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

Row sums of A380361.
Antidiagonal sums of A295633.
Cf. A005043, A346779, A380362.

A380360seq(36) \\ See PARI Link in A380362 for program code.

A380361 Triangle read by rows: T(n,k) is the number of embeddings on the sphere of Halin graphs on n unlabeled nodes with circuit rank k up to orientation-preserving homeomorphisms, 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, 4, 2, 1, 0, 0, 0, 4, 8, 3, 1, 0, 0, 0, 0, 12, 16, 3, 1, 0, 0, 0, 0, 6, 40, 25, 4, 1, 0, 0, 0, 0, 0, 43, 93, 40, 4, 1, 0, 0, 0, 0, 0, 19, 165, 197, 56, 5, 1, 0, 0, 0, 0, 0, 0, 143, 505, 364, 80, 5, 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 rotation.

			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, 4,  2,  1;
  10 | 0, 0, 0, 4,  8,  3,   1;
  11 | 0, 0, 0, 0, 12, 16,   3,   1;
  12 | 0, 0, 0, 0,  6, 40,  25,   4,  1;
  13 | 0, 0, 0, 0,  0, 43,  93,  40,  4,  1;
  14 | 0, 0, 0, 0,  0, 19, 165, 197, 56,  5,  1;
  ...

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

Row sums are A380360.
Column sums are A003455.
Main diagonal is A000012.
Central coefficients are A001683.
Cf. A295633, A380362.

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

PARI

Formula

Extensions

A380360 Number of embeddings on the sphere of Halin graphs on n unlabeled nodes up to orientation-preserving homeomorphisms.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

A380361 Triangle read by rows: T(n,k) is the number of embeddings on the sphere of Halin graphs on n unlabeled nodes with circuit rank k up to orientation-preserving homeomorphisms, 3 <= k <= n-1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula