Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).
%I #17 Dec 29 2017 10:31:47
%S 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,
%T 335,1,1,11,92,578,2126,3399,1144,1,1,12,126,1015,5481,16380,19228,
%U 3978,1,1,14,166,1641,11781,54132,129456,111041,14000
%N 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).
%C The polygon prior to dissection will have n*(k-2)+2 sides.
%C In the Harary, Palmer and Read reference these are the sequences called F.
%H Andrew Howroyd, <a href="/A295222/b295222.txt">Table of n, a(n) for n = 1..1275</a>
%H F. Harary, E. M. Palmer and R. C. Read, <a href="http://dx.doi.org/10.1016/0012-365X(75)90041-2">On the cell-growth problem for arbitrary polygons</a>, Discr. Math. 11 (1975), 371-389.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Fuss%E2%80%93Catalan_number">Fuss-Catalan number</a>
%F 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).
%F T(n,k) ~ n*A070914(n,k-2)/(n*(k-2)+2) for fixed k.
%e Array begins:
%e ===========================================================
%e n\k| 3 4 5 6 7 8
%e ---|-------------------------------------------------------
%e 1 | 1 1 1 1 1 1 ...
%e 2 | 1 1 1 1 1 1 ...
%e 3 | 3 5 6 8 9 11 ...
%e 4 | 10 22 40 64 92 126 ...
%e 5 | 30 116 285 578 1015 1641 ...
%e 6 | 99 612 2126 5481 11781 22386 ...
%e 7 | 335 3399 16380 54132 141778 317860 ...
%e 8 | 1144 19228 129456 548340 1753074 4638348 ...
%e 9 | 3978 111041 1043460 5672645 22137570 69159400 ...
%e 10 | 14000 650325 8544965 59653210 284291205 1048927880 ...
%e ...
%t u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
%t T[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#]&]/k;
%t 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_ *)
%o (PARI) \\ here u is Fuss-Catalan sequence with p = k+1.
%o u(n,k,r)={r*binomial((k - 1)*n + r, n)/((k - 1)*n + r)}
%o T(n,k)=sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d, k, k/d))/k;
%o for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);
%o (Python)
%o from sympy import binomial, gcd, totient, divisors
%o def u(n, k, r): return r*binomial((k - 1)*n + r, n)//((k - 1)*n + r)
%o def T(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
%o for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # _Indranil Ghosh_, Dec 13 2017, after PARI
%Y Columns k=3..5 are A003441, A005033, A005037.
%Y Cf. A033282, A070914, A295224, A295259, A295260.
%K nonn,tabl
%O 1,6
%A _Andrew Howroyd_, Nov 17 2017