OFFSET
1,6
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.
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
FORMULA
T(n,k) ~ A295222(n,k)/2 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 | 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 ...
...
MATHEMATICA
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 *)
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)}
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);
(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 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
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Nov 18 2017
STATUS
approved