A295224 -id:A295224 - cp's OEIS frontend

A001683 Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal vertices, all of degree 3 and hence n leaves).

1, 1, 1, 1, 4, 6, 19, 49, 150, 442, 1424, 4522, 14924, 49536, 167367, 570285, 1965058, 6823410, 23884366, 84155478, 298377508, 1063750740, 3811803164, 13722384546, 49611801980, 180072089896, 655977266884, 2397708652276, 8791599732140, 32330394085528

Offset: 2

N. J. A. Sloane

a(n) is the number of triangulations of an n-gon (equivalently, the number of vertices of the (n - 3)-dimensional associahedron) modulo the cyclic action [Bowman and Regev]. - N. J. A. Sloane, Dec 29 2012
a(n) is also the number of non-isomorphic cluster-tilted algebras of type A_(n-3), for n greater than or equal to 5. Equivalently it is the number of non-isomorphic quivers in the mutation class of any quiver with underlying graph A_(n-3) for n greater than or equal to 5. - Hermund A. Torkildsen (hermunda(AT)math.ntnu.no), Aug 06 2008
Number of oriented polyominoes composed of n-2 triangular cells of the hyperbolic regular tiling with Schläfli symbol {3,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 20 2024

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).

T. D. Noe, Table of n, a(n) for n=2..200
Marc J. Beauchamp, On Extremal Punctured Spheres, Dissertation, University of Pittsburgh, 2017.
F. R. Bernhart & N. J. A. Sloane, Correspondence, 1977
Douglas Bowman and Alon Regev, Counting symmetry classes of dissections of a convex regular polygon, arXiv preprint arXiv:1209.6270 [math.CO], 2012. See Th. 29(2).
William G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768.
W. G. Brown, Enumeration of Triangulations of the Disk, Proc. Lond. Math. Soc. s3-14 (1964) 746-768. [Annotated scanned copy]
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. See p. 163, line 4, but note that the formula given there has many typos (see the correct version given here).
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
O. Devillers, Vertex removal in two-dimensional Delauney triangulation: Speed-up by low degrees optimization, Comp. Geom. 44 (2011) 169.
Petr Gregor, Sven Jäger, Torsten Mütze, Joe Sawada, Kaja Wille, Gray codes and symmetric chains, arXiv:1802.06021 [math.CO], 2018.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
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.
C. O. Oakley and R. J. Wisner, Flexagons, The American Mathematical Monthly, Vol. 64, No. 3 (Mar., 1957), pp. 143-154
R. C. Read, On general dissections of a polygon, Preprint (1974)
Hermund A. Torkildsen, Counting cluster-tilted algebras of type A_n, International Electronic Journal of Algebra, 4, 2008, 149-158. [From Hermund A. Torkildsen (hermunda(AT)math.ntnu.no), Aug 06 2008]
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, J. Algebra and Applications, 12 (2013), #1250133. - From _N. J. A. Sloane_, Jan 22 2013

Column k=3 of A295224.
Cf. A007282, A057162.
A row or column of the array in A262586.
Polyominoes: A000207 (unoriented), A369314 (chiral), A208355(n-1) (achiral), A005034 {4,oo}, A007173 {3,3,oo}.

C := n->binomial(2*n,n)/(n+1); c := x->if whattype(x) = integer then C(x) else 0; fi; A001683 := n->C(n-2)/n + c(n/2-1)/2+(2/3)*c(n/3-1);

p=3; Table[Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) +If[OddQ[n], 0, Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1}]], {n, 0, 20}] (* Robert A. Russell, Dec 11 2004 *)
Rest[Rest[CoefficientList[Series[(6 + (1 - 4 x)^(3/2) + 6 x - 3(1 - 4 x^2)^(1/2) - 4 (1 - 4 x^3)^(1/2))/12, {x, 0, 33}], x]]] (* Vincenzo Librandi, Nov 25 2015 *)

Cat(n)=if(n==floor(n),return(binomial(2*n,n)/(n+1)));0
for(n=2,100,print1(Cat(n-2)/n+Cat(n/2-1)/2+(2/3)*Cat(n/3-1),", ")) \\ Derek Orr, Feb 26 2017

a(n) = C(n-2)/n + C(n/2-1)/2 + (2/3)*C(n/3-1), where C(n) = Catalan(n) (A000108) and terms are omitted if their subscripts are not integers.
G.f.: (6 + (1 - 4*x)^(3/2) + 6*x - 3*(1 - 4*x^2)^(1/2) - 4*(1 - 4*x^3)^(1/2))/12. - David Callan, Aug 01 2004
a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Mar 13 2016
a(n+2) = A000207(n) + A369314(n) = 2*A000207(n) - A208355(n-1) = 2*A369314(n) + A208355(n-1). - Robert A. Russell, Jan 19 2024
G.f.: z^2 * (4*G(z) - G(z)^2 + 3*G(z^2) + 4*z*G(z^3)) / 6, where G(z) = 1 + z*G(z)^2 is the g.f. for A000108. - Robert A. Russell, Apr 06 2024

A070914 Array read by antidiagonals giving number of paths up and left from (0,0) to (n,kn) where x/y <= k for all intermediate points.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 5, 1, 1, 1, 4, 12, 14, 1, 1, 1, 5, 22, 55, 42, 1, 1, 1, 6, 35, 140, 273, 132, 1, 1, 1, 7, 51, 285, 969, 1428, 429, 1, 1, 1, 8, 70, 506, 2530, 7084, 7752, 1430, 1, 1, 1, 9, 92, 819, 5481, 23751, 53820, 43263, 4862, 1, 1, 1, 10, 117, 1240

Offset: 0

Henry Bottomley, May 20 2002

Also related to dissections of polygons and enumeration of trees.
Number of dissections of a polygon into n (k+2)-gons by nonintersecting diagonals. All dissections are counted separately. See A295260 for nonequivalent solutions up to rotation and reflection. - Andrew Howroyd, Nov 20 2017
Number of rooted polyominoes composed of n (k+2)-gonal cells of the hyperbolic (Euclidean for k=0) regular tiling with Schläfli symbol {k+2,oo}. A rooted polyomino has one external edge identified, and chiral pairs are counted as two. For k>0, a stereographic projection of the {k+2,oo} tiling on the Poincaré disk can be obtained via the Christensson link. - Robert A. Russell, Jan 27 2024

			Rows start:
===========================================================
n\k| 0     1      2       3        4        5         6
---|-------------------------------------------------------
0  | 1,    1,     1,      1,       1,       1,        1 ...
1  | 1,    1,     1,      1,       1,       1,        1 ...
2  | 1,    2,     3,      4,       5,       6,        7 ...
3  | 1,    5,    12,     22,      35,      51,       70 ...
4  | 1,   14,    55,    140,     285,     506,      819 ...
5  | 1,   42,   273,    969,    2530,    5481,    10472 ...
6  | 1,  132,  1428,   7084,   23751,   62832,   141778 ...
7  | 1,  429,  7752,  53820,  231880,  749398,  1997688 ...
8  | 1, 1430, 43263, 420732, 2330445, 9203634, 28989675 ...
...

Alois P. Heinz, Antidiagonals n = 0..140, flattened
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
Peter Hilton and Jean Pedersen, Catalan Numbers, Their Generalization, and Their Uses, The Mathematical Intelligencer, March 1991, Volume 13, Issue 2, pp. 64-75.
V. E. Hoggatt, Jr. and M. Bicknell, Catalan and related sequences arising from inverses of Pascal's triangle matrices, Fib. Quart., 14 (1976), 395-405.

Rows include A000012 (twice), A000027, A000326.
Columns include A000012, A000108 (Catalan), A001764, A002293, A002294, A002295, A002296, A007556, A062994, A059968.
Reflected version of A062993 (which is the main entry).
Cf. A295260.
Polyominoes: A295224 (oriented), A295260 (unoriented).

A:= (n, k)-> binomial((k+1)*n, n)/(k*n+1):
seq(seq(A(n, d-n), n=0..d), d=0..12);  # Alois P. Heinz, Mar 25 2015

T[n_, k_] = Binomial[n(k+1), n]/(k*n+1); Flatten[Table[T[n-k, k], {n, 0, 9}, {k, n, 0, -1}]] (* Jean-François Alcover, Apr 08 2016 *)

T(n, k) = binomial(n*(k+1), n)/(n*k+1); \\ Andrew Howroyd, Nov 20 2017

T(n, k) = binomial(n*(k+1), n)/(n*k+1) = A071201(n, k*n) = A071201(n, k*n+1) = A071202(n, k*n+1) = A062993(n+k-1, k-1).

If P(k,x) = Sum_{n>=0} T(n,k)*x^n is the g.f. of column k (k>=0), then P(k,x) = exp(1/(k+1)*(Sum_{j>0} (1/j)*binomial((k+1)*j,j)*x^j)). - Werner Schulte, Oct 13 2015

A295260 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation and reflection (k >= 3).

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 2, 5, 4, 1, 1, 3, 8, 16, 12, 1, 1, 3, 12, 33, 60, 27, 1, 1, 4, 16, 68, 194, 261, 82, 1, 1, 4, 21, 112, 483, 1196, 1243, 228, 1, 1, 5, 27, 183, 1020, 3946, 8196, 6257, 733, 1, 1, 5, 33, 266, 1918, 10222, 34485, 58140, 32721, 2282

Offset: 1

Andrew Howroyd, Nov 18 2017

The polygon prior to dissection will have n*(k-2)+2 sides.
In the Harary, Palmer and Read reference these are the sequences called h.
T(n,k) is the number of unoriented polyominoes containing n k-gonal tiles of the hyperbolic regular tiling with Schläfli symbol {k,oo}. Stereographic projections of several of these tilings on the Poincaré disk can be obtained via the Christensson link. For unoriented polyominoes, chiral pairs are counted as one. T(n,2) could represent polyominoes of the Euclidean regular tiling with Schläfli symbol {2,oo}; T(n,2) = 1. - Robert A. Russell, Jan 21 2024

			Array begins:
  ===================================================
  n\k|   3     4      5       6        7        8
  ---|-----------------------------------------------
   1 |   1     1      1       1        1        1 ...
   2 |   1     1      1       1        1        1 ...
   3 |   1     2      2       3        3        4 ...
   4 |   3     5      8      12       16       21 ...
   5 |   4    16     33      68      112      183 ...
   6 |  12    60    194     483     1020     1918 ...
   7 |  27   261   1196    3946    10222    22908 ...
   8 |  82  1243   8196   34485   109947   290511 ...
   9 | 228  6257  58140  315810  1230840  3844688 ...
  10 | 733 32721 427975 2984570 14218671 52454248 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
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.
Wikipedia, Fuss-Catalan number

Columns k=3..7 are A000207, A005036, A005040, A004127, A005419.
Cf. A033282, A295222, A295259.
Polyominoes: A295224 (oriented), A070914 (rooted).

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
T[n_, k_] := (u[n, k, 1] + If[OddQ[n], u[(n - 1)/2, k, Quotient[k, 2]], If[OddQ[k], (u[n/2 - 1, k, k - 1] + u[n/2, k, 1])/2, u[n/2, k, 1]]] + (If[EvenQ[n], u[n/2, k, 1]] - u[n, k, 2])/2 + DivisorSum[GCD[n - 1, k], EulerPhi[#]*u[(n - 1)/#, k, k/#] &]/k)/2 /. Null -> 0;
Table[T[n - k + 2, k + 1], {n, 1, 11}, {k, n + 1, 2, -1}] // Flatten (* Jean-François Alcover, Dec 28 2017, after Andrew Howroyd *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n,k,r) = {r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n,k) = {(u(n,k,1) + if(n%2, u((n-1)/2,k,k\2), if(k%2, (u(n/2-1,k,(k-1)) + u(n/2,k,1))/2, u(n/2,k,1))) + (if(n%2==0, u(n/2,k,1))-u(n,k,2))/2 + sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d,k,k/d))/k)/2}
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

T(n,k) ~ A295222(n,k)/(2*n) for fixed k.

A005034 Number of nonequivalent dissections of a polygon into n quadrilaterals by nonintersecting diagonals up to rotation.

Original entry on oeis.org

1, 1, 1, 2, 7, 25, 108, 492, 2431, 12371, 65169, 350792, 1926372, 10744924, 60762760, 347653944, 2009690895, 11723100775, 68937782355, 408323229930, 2434289046255, 14598011263089, 88011196469040, 533216750567280, 3245004785069892, 19829768942544276, 121639211516546668

Offset: 0

N. J. A. Sloane

Also, with a different offset, number of colored quivers in the 2-mutation class of a quiver of Dynkin type A_n. - N. J. A. Sloane, Jan 22 2013
Closed formula is given in my paper linked below. - Nikos Apostolakis, Aug 01 2018
Number of oriented polyominoes composed of n square cells of the hyperbolic regular tiling with Schläfli symbol {4,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 20 2024

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 290.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

G. C. Greubel, Table of n, a(n) for n = 0..1000
Nikos Apostolakis, Non-crossing trees, quadrangular dissections, ternary trees, and duality preserving bijections, arXiv:1807.11602 [math.CO], July 2018.
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Quebec 16 (1992), no 1, 53-80.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
Alexander Stoimenow, On the number of chord diagrams, Discr. Math. 218 (2000), 209-233. See p. 232.
Torkildsen, Hermund A., Colored quivers of type A and the cell-growth problem, J. Algebra and Applications, 12 (2013), #1250133.

Column k=4 of A295224.

Polyominoes: A005036 (unoriented), A369315 (chiral), A047749 (achiral), A385149 (asymmetric), A001764 (rooted), A001683(n+2) {3,oo}, A005038 {5,oo}.

p=4; Table[Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) +If[OddQ[n], 0, Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1}]], {n, 0, 20}] (* Robert A. Russell, Dec 11 2004 *)
Table[(3Binomial[3n,n]/(2n+1)-Binomial[3n+1,n]/(n+1)-If[OddQ[n],-2Binomial[(3n-1)/2,(n-1)/2]-If[1==Mod[n,4],4Binomial[(3n-3)/4,(n-1)/4],0],-2Binomial[3n/2,n/2]]/(n+1))/4,{n,0,30}] (* Robert A. Russell, Jun 19 2025 *)

a(n) ~ 3^(3*n + 1/2) / (sqrt(Pi) * n^(5/2) * 2^(2*n + 3)). - Vaclav Kotesovec, Mar 13 2016
a(n) = A005036(n) + A369315(n) = 2*A005036(n) - A047749(n) = 2*A369315(n) + A047749(n). - Robert A. Russell, Jan 19 2024
G.f.: (3*G(z) - G(z)^2 + 2*G(z^2) + z*G(z^2)^2 + 2z*G(z^4)) / 4, where G(z)=1+z*G(z)^3 is the g.f. for A001764. - Robert A. Russell, Jun 19 2025

Name clarified by Andrew Howroyd, Nov 20 2017

A005038 Number of nonequivalent dissections of a polygon into n pentagons by nonintersecting diagonals up to rotation.

Original entry on oeis.org

1, 1, 2, 12, 57, 366, 2340, 16252, 115940, 854981, 6444826, 49554420, 387203390, 3068067060, 24604111560, 199398960212, 1631041938108, 13451978877748, 111765327780200, 934774244822704, 7865200653146905

Offset: 1

N. J. A. Sloane

Also, with a different offset, number of colored quivers in the 3-mutation class of a quiver of Dynkin type A_n. - N. J. A. Sloane, Jan 22 2013

Number of oriented polyominoes composed of n pentagonal cells of the hyperbolic regular tiling with Schläfli symbol {5,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For oriented polyominoes, chiral pairs are counted as two. - Robert A. Russell, Jan 23 2024

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

G. C. Greubel, Table of n, a(n) for n = 1..1000
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
F. Harary, E. M. Palmer, R. C. Read, On the cell-growth problem for arbitrary polygons, computer printout, circa 1974
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, arXiv:1004.4512 [math.RT], 2010.
Hermund A. Torkildsen, Colored quivers of type A and the cell-growth problem, J. Algebra and Applications, 12 (2013), #1250133. - From _N. J. A. Sloane_, Jan 22 2013

Column k=5 of A295224.

Polyominoes: A005040 (unoriented), A369471 (chiral), A369472 (achiral), A001683(n+2) {3,oo}, A005034 {4,oo}, A221184{n-1} {6,oo}.

p=5; Table[Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) +If[OddQ[n], 0, Binomial[(p-1)n/2, n/2]/((p-2)n+2)]+Plus @@ Map[EulerPhi[ # ]Binomial[((p-1)n+1)/#, (n-1)/# ]/((p-1)n+1)&, Complement[Divisors[GCD[p, n-1]], {1}]], {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)

a(n) ~ 2^(8*n + 1/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n + 5/2)). - Vaclav Kotesovec, Mar 13 2016

a(n) = A005040(n) + A369471(n) = 2*A005040(n) - A369472(n) = 2*A369471(n) + A369472(n). - Robert A. Russell, Jan 23 2024

a(21) corrected by Sean A. Irvine, Mar 11 2016

Name edited by Andrew Howroyd, Nov 20 2017

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 1, 1, 5, 10, 1, 1, 6, 22, 30, 1, 1, 8, 40, 116, 99, 1, 1, 9, 64, 285, 612, 335, 1, 1, 11, 92, 578, 2126, 3399, 1144, 1, 1, 12, 126, 1015, 5481, 16380, 19228, 3978, 1, 1, 14, 166, 1641, 11781, 54132, 129456, 111041, 14000

Offset: 1

Andrew Howroyd, Nov 17 2017

The polygon prior to dissection will have n*(k-2)+2 sides.

In the Harary, Palmer and Read reference these are the sequences called F.

			Array begins:
  ===========================================================
  n\k|     3      4       5        6         7          8
  ---|-------------------------------------------------------
   1 |     1      1       1        1         1          1 ...
   2 |     1      1       1        1         1          1 ...
   3 |     3      5       6        8         9         11 ...
   4 |    10     22      40       64        92        126 ...
   5 |    30    116     285      578      1015       1641 ...
   6 |    99    612    2126     5481     11781      22386 ...
   7 |   335   3399   16380    54132    141778     317860 ...
   8 |  1144  19228  129456   548340   1753074    4638348 ...
   9 |  3978 111041 1043460  5672645  22137570   69159400 ...
  10 | 14000 650325 8544965 59653210 284291205 1048927880 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Wikipedia, Fuss-Catalan number

Columns k=3..5 are A003441, A005033, A005037.

Cf. A033282, A070914, A295224, A295259, A295260.

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
T[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#]&]/k;
Table[T[n - k + 3, k], {n, 1, 10}, {k, n + 2, 3, -1}] // Flatten (* Jean-François Alcover, Nov 21 2017, after Andrew Howroyd *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n,k,r)={r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n,k)=sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d, k, k/d))/k;
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

from sympy import binomial, gcd, totient, divisors
def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
def T(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # Indranil Ghosh, Dec 13 2017, after PARI

T(n,k) = Sum_{d|gcd(n-1,k)} phi(d)*u((n-1)/d, k, k/d)/k where u(n,k,r) = r*binomial((k - 1)*n + r, n)/((k - 1)*n + r).

T(n,k) ~ n*A070914(n,k-2)/(n*(k-2)+2) for fixed k.

A295259 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation and reflection (k >= 3).

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 1, 1, 4, 6, 1, 1, 4, 13, 16, 1, 1, 6, 22, 64, 52, 1, 1, 6, 35, 147, 315, 170, 1, 1, 8, 49, 302, 1074, 1727, 579, 1, 1, 8, 67, 518, 2763, 8216, 9658, 1996, 1, 1, 10, 87, 843, 5916, 27168, 64798, 55657, 7021

Offset: 1

Andrew Howroyd, Nov 18 2017

The polygon prior to dissection will have n*(k-2)+2 sides.

In the Harary, Palmer and Read reference these are the sequences called f.

			Array begins:
  =========================================================
  n\k|    3      4       5        6         7         8
  ---|-----------------------------------------------------
   1 |    1      1       1        1         1         1 ...
   2 |    1      1       1        1         1         1 ...
   3 |    2      4       4        6         6         8 ...
   4 |    6     13      22       35        49        67 ...
   5 |   16     64     147      302       518       843 ...
   6 |   52    315    1074     2763      5916     11235 ...
   7 |  170   1727    8216    27168     70984    159180 ...
   8 |  579   9658   64798   274360    876790   2319678 ...
   9 | 1996  55657  521900  2837208  11069760  34582800 ...
  10 | 7021 325390 4272967 29828330 142148343 524470485 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Wikipedia, Fuss-Catalan number

Columns k=3..5 are A003446, A005035, A005039.

Cf. A033282, A070914, A295222, A295224, A295260.

u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
F[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#] &]/k;
T[n_, k_] := (F[n, k] + If[OddQ[k], If[OddQ[n], u[(n-1)/2, k, (k-1)/2], u[n/2-1, k, k-1]], If[OddQ[n], u[(n-1)/2, k, k/2+1], u[n/2-1, k, k]]])/2;
Table[T[n-k-1, k], {n, 1, 14}, {k, n-2, 3, -1}] // Flatten (* Jean-François Alcover, Jan 19 2018, translated from PARI *)

\\ here u is Fuss-Catalan sequence with p = k+1.
u(n,k,r) = {r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
F(n,k) = {sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d,k,k/d))/k}
T(n,k) = {(F(n,k) + if(k%2, if(n%2, u((n-1)/2,k,(k-1)/2), u(n/2-1,k,(k-1))), if(n%2, u((n-1)/2,k,k/2+1), u(n/2-1,k,k)) ))/2;}
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

from sympy import binomial, gcd, totient, divisors
def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
def F(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
def T(n, k): return (F(n, k) + ((u((n - 1)//2, k, (k - 1)//2) if n%2 else u(n//2 - 1, k, k - 1)) if k%2 else (u((n - 1)//2, k, k//2 + 1) if n%2 else u(n//2 - 1, k, k))))//2
for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # Indranil Ghosh, Dec 13 2017, after PARI code

T(n,k) ~ A295222(n,k)/2 for fixed k.

A370062 Array read by antidiagonals: T(n,k) is the number of achiral dissections of a polygon into n k-gons by nonintersecting diagonals, n >= 1, k >= 3.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 3, 2, 1, 1, 3, 4, 7, 5, 1, 1, 3, 5, 9, 12, 5, 1, 1, 4, 6, 18, 22, 30, 14, 1, 1, 4, 7, 21, 35, 52, 55, 14, 1, 1, 5, 8, 34, 51, 136, 140, 143, 42, 1, 1, 5, 9, 38, 70, 190, 285, 340, 273, 42, 1, 1, 6, 10, 55, 92, 368, 506, 1155, 969, 728, 132

Offset: 1

Andrew Howroyd, Feb 08 2024

The polygon prior to dissection will have n*(k-2)+2 sides.

			Array begins:
=============================================
n\k|  3   4   5    6    7    8    9    10 ...
---+-----------------------------------------
1  |  1   1   1    1    1    1    1     1 ...
2  |  1   1   1    1    1    1    1     1 ...
3  |  1   2   2    3    3    4    4     5 ...
4  |  2   3   4    5    6    7    8     9 ...
5  |  2   7   9   18   21   34   38    55 ...
6  |  5  12  22   35   51   70   92   117 ...
7  |  5  30  52  136  190  368  468   775 ...
8  | 14  55 140  285  506  819 1240  1785 ...
9  | 14 143 340 1155 1950 4495 6545 12350 ...
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 antidiagonals)
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
Wikipedia, Fuss-Catalan number

Columns are A208355(n-1), A047749 (k=4), A369472 (k=5), A143546 (k=6), A143547 (k=8), A143554 (k=10), A192893 (k=12).

Cf. A070914 (rooted), A295224 (oriented), A295260 (unoriented), A369929, A370060 (achiral rooted at cell).

\\ here u is Fuss-Catalan sequence with p = k-1.
u(n, k, r) = {r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
T(n, k) = {(if(n%2, u((n-1)/2, k, k\2), if(k%2, u(n/2-1, k, k-1), u(n/2, k, 1))))}
for(n=1, 9, for(k=3, 10, print1(T(n, k), ", ")); print);

T(n,k) = 2*A295260(n,k) - A295224(n,k).
T(n,2*k+1) = A370060(n,2*k+1).
T(n,2*k) = A369929(n,2*k-1).

A003455 Number of nonequivalent dissections of an n-gon by nonintersecting diagonals up to rotation.

Original entry on oeis.org

1, 2, 3, 11, 29, 122, 479, 2113, 9369, 43392, 203595, 975563, 4736005, 23296394, 115811855, 581324861, 2942579633, 15008044522, 77064865555, 398150807179, 2068470765261, 10800665952376, 56658467018647, 298489772155137, 1578702640556193

Offset: 3

N. J. A. Sloane

nonn

Total number of dissections of an n-gon into polygons without reflection. - Sean A. Irvine, May 15 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, A003456, A005034, A295224, A295495.

\\ See A295495 for DissectionsModCyclic().
DissectionsModCyclic(apply(v->1, [1..30])) \\ Andrew Howroyd, Nov 22 2017

More terms from Sean A. Irvine, May 15 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)

cp's OEIS Frontend

A001683 Number of one-sided triangulations of the disk; or flexagons of order n; or unlabeled plane trivalent trees (n-2 internal vertices, all of degree 3 and hence n leaves).

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A070914 Array read by antidiagonals giving number of paths up and left from (0,0) to (n,kn) where x/y <= k for all intermediate points.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A295260 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation and reflection (k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A005034 Number of nonequivalent dissections of a polygon into n quadrilaterals by nonintersecting diagonals up to rotation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A005038 Number of nonequivalent dissections of a polygon into n pentagons by nonintersecting diagonals up to rotation.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A295222 Array read by antidiagonals: T(n,k) is the number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation (k >= 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Python

Formula

A295259 Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation and reflection (k >= 3).

Views

Author

Keywords