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

1, 1, 1, 1, 1, 1, 1, 1, 2, 4, 1, 1, 2, 7, 6, 1, 1, 3, 12, 25, 19, 1, 1, 3, 19, 57, 108, 49, 1, 1, 4, 26, 118, 366, 492, 150, 1, 1, 4, 35, 203, 931, 2340, 2431, 442, 1, 1, 5, 46, 332, 1989, 7756, 16252, 12371, 1424, 1, 1, 5, 57, 494, 3766, 20254, 68685, 115940, 65169, 4522

Offset

1,9

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 oriented 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 oriented polyominoes, chiral pairs are counted as two. 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

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

Formula

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

Example

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 |    4     7     12      19       26        35 ...
   5 |    6    25     57     118      203       332 ...
   6 |   19   108    366     931     1989      3766 ...
   7 |   49   492   2340    7756    20254     45448 ...
   8 |  150  2431  16252   68685   219388    580203 ...
   9 |  442 12371 115940  630465  2459730   7684881 ...
  10 | 1424 65169 854981 5966610 28431861 104898024 ...
  ...

Mathematica

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

Prog

(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==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;
for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);
(Python)
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 u(n, k, 1) + ((u(n//2, k, 1) if n%2==0 else 0) - u(n, k, 2))//2 + 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 code

Crossrefs

Columns k=3..6 are A001683(n+2), A005034, A005038, A221184(n-1).

Cf. A033282, A070914, A295222, A295259, A295260.

Polyominoes: A295260 (unoriented), A070914 (rooted).

Sequence in context: A007738 A186520 A158570 * A074749 A194524 A117136

Adjacent sequences: A295221 A295222 A295223 * A295225 A295226 A295227

Keyword

nonn,tabl

Author

Andrew Howroyd, Nov 17 2017

Status

approved