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

Author

Andrew Howroyd, Nov 18 2017

Keywords

• nonn
• tabl

Comments

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

Examples

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

Links

• 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

Crossrefs

Columns k=3..7 are A000207, A005036, A005040, A004127, A005419.

Cf. A033282, A295222, A295259.

Polyominoes: A295224 (oriented), A070914 (rooted).

Programs

Mathematica

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

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)}
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);

Formula

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