A005419 -id:A005419 - cp's OEIS frontend

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

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.

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

Original entry on oeis.org

1, 1, 2, 5, 16, 60, 261, 1243, 6257, 32721, 175760, 963900, 5374400, 30385256, 173837631, 1004867079, 5861610475, 34469014515, 204161960310, 1217145238485, 7299007647552, 44005602441840

Offset: 1

N. J. A. Sloane

Closed formula is given in my paper linked below. - Nikos Apostolakis, Aug 01 2018

Number of unoriented 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 unoriented polyominoes, chiral pairs are counted as one. - Robert A. Russell, Jan 20 2024

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 = 1..100
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, and 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. V. Konstantinova, A survey of the cell-growth problem and some its variations, Com 2 MaC-KOSEF, 2001. (Archived link.)
Index entries for "core" sequences

Column k=4 of A295260.
Cf. A005419, A004127.
Polyominoes: A005034 (oriented), A369315 (chiral), A047749 (achiral), A385149 (asymmetric), A001764 (rooted), A000207 {3,oo}, A005040 {5,oo}, A005038 {5,oo} (oriented).

p=4; Table[(Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) + If[OddQ[n], If[OddQ[p], Binomial[(p-1)n/2, (n-1)/2]/n, (p+1)Binomial[((p-1)n-1)/2, (n-1)/2]/((p-2)n+2)], 3Binomial[(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, 2}]])/2, {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)
Table[(3Binomial[3n,n]/(2n+1)-Binomial[3n+1,n]/(n+1)-If[OddQ[n],-10Binomial[(3n-1)/2,(n-1)/2]-If[1==Mod[n,4],4Binomial[(3n-3)/4,(n-1)/4],0],-6Binomial[3n/2,n/2]]/(n+1))/8,{n,0,30}] (* Robert A. Russell, Jun 19 2025 *)

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

More terms from Sascha Kurz, Oct 13 2001

Name edited by Andrew Howroyd, Nov 20 2017

A004127 Number of planar hexagon trees with n hexagons.

Original entry on oeis.org

1, 1, 3, 12, 68, 483, 3946, 34485, 315810, 2984570, 28907970, 285601251, 2868869733, 29227904840, 301430074416, 3141985563575, 33059739636198, 350763452126835, 3749420616902637, 40348040718155170, 436827335493148600

Offset: 1

N. J. A. Sloane

nonn

Number of nonequivalent dissections of a polygon into n hexagons by nonintersecting diagonals up to rotation and reflection. - Andrew Howroyd, Nov 20 2017

Number of unoriented polyominoes composed of n hexagonal cells of the hyperbolic regular tiling with Schläfli symbol {6,oo}. A stereographic projection of this tiling on the Poincaré disk can be obtained via the Christensson link. For unoriented polyominoes, chiral pairs are counted as one. - 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..925
Malin Christensson, Make hyperbolic tilings of images, web page, 2019.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147.
L. W. Beineke and R. E. Pippert, On the enumeration of planar trees of hexagons, Glasgow Math. J., 15 (1974), 131-147. [Annotated scanned copy]
Index entries for sequences related to trees

Column k=6 of A295260.
Cf. A002294.
Polyominoes: A221184{n-1} (oriented), A369473 (chiral), A143546 (achiral), A005040 {5,oo}, A005419 {7,oo}.

T := proc(n) if floor(n)=n then binomial(5*n+1,n)/(5*n+1) else 0 fi end: U := proc(n) if n mod 2 = 0 then binomial(5*n/2+1, n/2)/(5*n/2+1) else 6*binomial((5*n+1)/2,(n-1)/2)/(5*n+1) fi end: S := n->T(n)/4/(2*n+1)+T(n/2)/6+(5*n-2)*T((n-1)/3)/6/(2*n+1)+T((n-1)/6)/6+7*U(n)/12: seq(S(n),n=1..25); (Emeric Deutsch)

p=6; Table[(Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) + If[OddQ[n], If[OddQ[p], Binomial[(p-1)n/2, (n-1)/2]/n, (p+1)Binomial[((p-1)n-1)/2, (n-1)/2]/((p-2)n+2)], 3Binomial[(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, 2}]])/2, {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)

See Theorem 3 on p. 142 in the Beineke-Pippert paper; also the Maple and Mathematica codes here.
a(n) ~ 5^(5*n + 1/2) / (sqrt(Pi) * n^(5/2) * 2^(8*n + 13/2)). - Vaclav Kotesovec, Mar 13 2016
a(n) = A221184(n-1) - A369473(n) = (A221184(n-1) + A143546(n)) / 2 = A369473(n) + A143546(n). - Robert A. Russell, Jan 23 2024

More terms from Emeric Deutsch, Jan 22 2004

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

Original entry on oeis.org

1, 1, 2, 8, 33, 194, 1196, 8196, 58140, 427975, 3223610, 24780752, 193610550, 1534060440, 12302123640, 99699690472, 815521503060, 6725991120004, 55882668179880, 467387136083296, 3932600361607809, 33269692212847056, 282863689410850236, 2415930985594609548

Offset: 1

N. J. A. Sloane

nonn

Number of unoriented 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 unoriented polyominoes, chiral pairs are counted as one. - 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.
E. V. Konstantinova, A survey of the cell-growth problem and some its variations, preprint, 2001.
E. V. Konstantinova, Com2Mac - Preprints [Dead link?]

Column k=5 of A295260.

Polyominoes: A005038 (oriented), A369471 (chiral), A369472 (achiral), A000207 {3,oo}, A005036 {4,oo}, A004127 {6,oo}, A005419 {7,oo}.

p=5; Table[(Binomial[(p-1)n, n]/(((p-2)n+1)((p-2)n+2)) + If[OddQ[n], If[OddQ[p], Binomial[(p-1)n/2, (n-1)/2]/n, (p+1)Binomial[((p-1)n-1)/2, (n-1)/2]/((p-2)n+2)], 3Binomial[(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, 2}]])/2, {n, 1, 20}] (* Robert A. Russell, Dec 11 2004 *)

See Mathematica code.
a(n) ~ 2^(8*n - 1/2) / (sqrt(Pi) * n^(5/2) * 3^(3*n + 5/2)). - Vaclav Kotesovec, Mar 13 2016
a(n) = A005038(n) - A369471(n) = (A005038(n) + A369472(n)) / 2 = A369471(n) + A369472(n). - Robert A. Russell, Jan 23 2024

More terms from Sascha Kurz, Oct 13 2001.

Name edited by Andrew Howroyd, Nov 20 2017.

A173496 Partial sums of A005036.

Original entry on oeis.org

1, 2, 4, 9, 25, 85, 346, 1589, 7846, 40567, 216327, 1180227, 6554627, 36939883, 210777514, 1215644593, 7077255068, 41546269583, 245708229893, 1462853468378, 8761861115930, 52767463557770

Offset: 1

Jonathan Vos Post, Feb 19 2010

nonn

Partial sums of number of ways of dissecting a polygon into n quadrilaterals. The subsequence of primes in this partial sum begins: 2, 6554627, 36939883, 1215644593.

			a(22) = 1 + 1 + 2 + 5 + 16 + 60 + 261 + 1243 + 6257 + 32721 + 175760 + 963900 + 5374400 + 30385256 + 173837631 + 1004867079 + 5861610475 + 34469014515 + 204161960310 + 1217145238485 + 7299007647552 + 44005602441840.

Cf. A005036, A005419, A004127, A005038, A005040, A000207.

a(n) = SUM[i=1..n] A005036(i).

cp's OEIS Frontend

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

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A004127 Number of planar hexagon trees with n hexagons.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A173496 Partial sums of A005036.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula