A003455 -id:A003455 - cp's OEIS frontend

A001004 Number of nonequivalent dissections of an (n+2)-gon by nonintersecting diagonals up to rotation and reflection.

1, 1, 2, 3, 9, 20, 75, 262, 1117, 4783, 21971, 102249, 489077, 2370142, 11654465, 57916324, 290693391, 1471341341, 7504177738, 38532692207, 199076194985, 1034236705992, 5400337050086, 28329240333758, 149244907249629

Offset: 0

N. J. A. Sloane

Original name: number of symmetric dissections of a polygon.

Also number of 2-connected outerplanar graphs on n unlabeled nodes. - Steven Finch, Dec 09 2004

Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155--183. MR0891613 (89a:05009). See p. 155. - N. J. A. Sloane, Apr 18 2014
Guanzhang Hu, Group theory method for enumeration of outerplanar graphs, Acta Math. Appl. Sinica 14 (1998) 381-387.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
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 = 0..200
S. R. Finch, Planar graph growth constants.
Steven R. Finch, Planar graph growth constants [Cached copy, with permission of the author]
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.
P. Lisonek, Closed forms for the number of polygon dissections, Journal of Symbolic Computation 20 (1995), 595-601.
T. Motzkin, The hypersurface cross ratio, Bull. Amer. Math. Soc., 51 (1945), 976-984.
T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, Bull. Amer. Math. Soc., 54 (1948), 352-360.
R. C. Read, On general dissections of a polygon, Preprint (1974)
Ronald C. Read, On general dissections of a polygon, Aequat. math. 18 (1978) 370-388.
James Tilley, Stan Wagon, and Eric Weisstein, A Catalog of Facially Complete Graphs, arXiv:2409.11249 [math.CO], 2024. See pp. 7,11.

Cf. A003454, A003455, A003456, A005036, A295260.

f[x_, n_]:=x+Sum[(1/r)*Binomial[s-2, r-1]*Binomial[r+s-1, s]*x^s, {r, 1, n}, {s, 2, n}]; F[x_, n_]:=Series[((3x^2-2*x*f[x, n]+f[x, n]^2)- (2+2*x+7*x^2-4*x*f[x, n]+2*f[x, n]^2)*f[x^2, n]+ 2*f[x^2, n]^2)/(4*(2*f[x^2, n]-1))+Sum[If[Mod[k, d]==0, EulerPhi[d]*f[x^d, n]^(k/d)/k, 0], {k, 3, n}, {d, 1, k}]/2, {x, 0, n}]; F[x, 22] (Finch)

\\ See A295419 for DissectionsModDihedral().
my(v=DissectionsModDihedral(apply(i->1, [1..30])));v[3..#v] \\ Andrew Howroyd, Nov 22 2017

More terms from Esa Peuha (esa.peuha(AT)helsinki.fi), Oct 21 2005

Name clarified by Andrew Howroyd, Nov 22 2017

A003454 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals rooted at a cell up to rotation.

Original entry on oeis.org

1, 2, 6, 25, 107, 509, 2468, 12258, 61797, 315830, 1630770, 8498303, 44629855, 235974495, 1255105304, 6710883952, 36050676617, 194478962422, 1053120661726, 5722375202661, 31191334491891, 170504130213135, 934495666529380, 5134182220623958, 28270742653671621

Offset: 3

N. J. A. Sloane

nonn

Total number of dissections of an n-gon into polygons without reflection and rooted at a cell. - Sean A. Irvine, May 14 2015

Say two n-gons are equivalent (or in the same convexity class) if there is a bijection between the edges and vertices which preserves inclusion of vertices and edges, preserves the handedness of the polygon (does not reflect the polygon over a line), maps vertices of the convex hulls to each other, and induces an equivalence on each nontrivially connected component of Hull(X) \ X. This sequence is the number of convexity classes for an n-gon, up to rotation. - Griffin N. Macris, Mar 02 2021

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 = 3..200
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.

Cf. A001004, A003455, A003456, A005033, A295222.

Cf. A003442.

\\ See A003442 for DissectionsModCyclicRooted.
DissectionsModCyclicRooted(apply(i->1, [1..30])) \\ Andrew Howroyd, Nov 22 2017

G.f.: -f(x) - (f(x)^2 + f(x^2))/2 + Sum_{k>=1} (phi(k)/k)*log(1/(1 - f(x^k))), where phi(k) is Euler's Totient function and f(x) = (1 + x - sqrt(1 - 6x + x^2))/4 is related to the o.g.f. for A001003. - Griffin N. Macris, Mar 02 2021

More terms from Sean A. Irvine, May 14 2015

Name clarified by Andrew Howroyd, Nov 22 2017

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)

A003456 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals rooted at a cell up to rotation and reflection.

Original entry on oeis.org

1, 2, 5, 17, 62, 275, 1272, 6225, 31075, 158376, 816229, 4251412, 22319056, 117998524, 627573216, 3355499036, 18025442261, 97239773408, 526560862829, 2861189112867, 15595669996482, 85252072993968, 467247847612316, 2567091151780343

Offset: 3

N. J. A. Sloane

nonn

Total number of dissections of an n-gon into polygons with reflection and rooted at a cell. - Sean A. Irvine, May 14 2015

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 = 3..200
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.

Cf. A001004, A003454, A003455, A005035, A295259.

\\ See A003447 for DissectionsModDihedralRooted()
DissectionsModDihedralRooted(apply(i->1, [1..30]))

More terms from Sean A. Irvine, May 14 2015
Name clarified by Andrew Howroyd, Nov 24 2017
a(15) corrected by Andrew Howroyd, Nov 24 2017

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

Original entry on oeis.org

1, 1, 2, 5, 11, 36, 114, 410, 1458, 5488, 20786, 80770, 317378, 1265139, 5094139, 20718347, 84961256, 351086326, 1460591637, 6113826319, 25733864299, 108867782794, 462707558813, 1974991841442, 8463121111860, 36397780088126, 157066702354947, 679917566925030

Offset: 3

Andrew Howroyd, Nov 22 2017

nonn

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. A003455, A295224, A295419.

DissectionsModCyclic[v_] :=
Module[{n = Length[v], q, vars, u, 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]; p = O[x]^n + x u[1, 1] - x^2 + (u[2, 1] - u[1, 2])/2 + Sum[v[[i]] Sum[EulerPhi[d] u[d, i/d]/i, {d, Divisors[i]}], {i, 3, Length[v]}]; Drop[CoefficientList[p, x], 3]];
DissectionsModCyclic[Boole[PrimeQ[#]]& /@ Range[1, 31]] (* Jean-François Alcover, Sep 26 2019, after Andrew Howroyd *)

\\ number of dissections into parts defined by set.
DissectionsModCyclic(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(p=O(x*x^n) + x*u(1,1) - x^2 + (u(2,1)-u(1,2))/2 + sum(i=3, #v, my(c=v[i]); if(c,c*sumdiv(i, d, eulerphi(d)*u(d,i/d))/i)));
vector(n, i, polcoeff(p, i))}
DissectionsModCyclic(apply(i->isprime(i), [1..30]))

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

A001004 Number of nonequivalent dissections of an (n+2)-gon by nonintersecting diagonals up to rotation and reflection.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A003454 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals rooted at a cell up to rotation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

A003456 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals rooted at a cell up to rotation and reflection.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

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