login
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).
9
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,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
F. Harary, E. M. Palmer and R. C. Read, On the cell-growth problem for arbitrary polygons, Discr. Math. 11 (1975), 371-389.
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.
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 | 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 ...
...
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 *)
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)=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
CROSSREFS
Columns k=3..5 are A003441, A005033, A005037.
Sequence in context: A201588 A336858 A086385 * A362078 A123162 A213998
KEYWORD
nonn,tabl
AUTHOR
Andrew Howroyd, Nov 17 2017
STATUS
approved