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

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

Author

Andrew Howroyd, Nov 17 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 F.

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

Links

• 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

Crossrefs

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

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

Programs

Mathematica

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

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

Formula

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.