|
%I #12 Jan 19 2018 06:03:10
%S 1,1,1,1,1,2,1,1,4,6,1,1,4,13,16,1,1,6,22,64,52,1,1,6,35,147,315,170,
%T 1,1,8,49,302,1074,1727,579,1,1,8,67,518,2763,8216,9658,1996,1,1,10,
%U 87,843,5916,27168,64798,55657,7021
%N Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals rooted at a cell up to rotation and reflection (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="/A295259/b295259.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) ~ A295222(n,k)/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 | 2 4 4 6 6 8 ...
%e 4 | 6 13 22 35 49 67 ...
%e 5 | 16 64 147 302 518 843 ...
%e 6 | 52 315 1074 2763 5916 11235 ...
%e 7 | 170 1727 8216 27168 70984 159180 ...
%e 8 | 579 9658 64798 274360 876790 2319678 ...
%e 9 | 1996 55657 521900 2837208 11069760 34582800 ...
%e 10 | 7021 325390 4272967 29828330 142148343 524470485 ...
%e ...
%t u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);
%t F[n_, k_] := DivisorSum[GCD[n-1, k], EulerPhi[#]*u[(n-1)/#, k, k/#] &]/k;
%t 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;
%t 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 *)
%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 F(n,k) = {sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d,k,k/d))/k}
%o 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;}
%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 F(n, k): return sum([totient(d)*u((n - 1)//d, k, k//d) for d in divisors(gcd(n - 1, k))])//k
%o 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
%o for n in range(1, 11): print([T(n, k) for k in range(3, 9)]) # _Indranil Ghosh_, Dec 13 2017, after PARI code
%Y Columns k=3..5 are A003446, A005035, A005039.
%Y Cf. A033282, A070914, A295222, A295224, A295260.
%K nonn,tabl
%O 1,6
%A _Andrew Howroyd_, Nov 18 2017
|
