login
Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals up to rotation and reflection (k >= 3).
16

%I #17 Jan 28 2024 09:21:15

%S 1,1,1,1,1,1,1,1,2,3,1,1,2,5,4,1,1,3,8,16,12,1,1,3,12,33,60,27,1,1,4,

%T 16,68,194,261,82,1,1,4,21,112,483,1196,1243,228,1,1,5,27,183,1020,

%U 3946,8196,6257,733,1,1,5,33,266,1918,10222,34485,58140,32721,2282

%N Array read by antidiagonals: T(n,k) = number of nonequivalent dissections of a polygon into n k-gons by nonintersecting diagonals 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 h.

%C T(n,k) is the number of unoriented polyominoes containing n k-gonal tiles of the hyperbolic regular tiling with Schläfli symbol {k,oo}. Stereographic projections of several of these tilings on the Poincaré disk can be obtained via the Christensson link. For unoriented polyominoes, chiral pairs are counted as one. T(n,2) could represent polyominoes of the Euclidean regular tiling with Schläfli symbol {2,oo}; T(n,2) = 1. - _Robert A. Russell_, Jan 21 2024

%H Andrew Howroyd, <a href="/A295260/b295260.txt">Table of n, a(n) for n = 1..1275</a>

%H Malin Christensson, <a href="http://malinc.se/m/ImageTiling.php">Make hyperbolic tilings of images</a>, web page, 2019.

%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 E. Krasko, A. Omelchenko, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v22i1p17">Brown's Theorem and its Application for Enumeration of Dissections and Planar Trees</a>, The Electronic Journal of Combinatorics, 22 (2015), #P1.17.

%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*n) 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 | 1 2 2 3 3 4 ...

%e 4 | 3 5 8 12 16 21 ...

%e 5 | 4 16 33 68 112 183 ...

%e 6 | 12 60 194 483 1020 1918 ...

%e 7 | 27 261 1196 3946 10222 22908 ...

%e 8 | 82 1243 8196 34485 109947 290511 ...

%e 9 | 228 6257 58140 315810 1230840 3844688 ...

%e 10 | 733 32721 427975 2984570 14218671 52454248 ...

%e ...

%t u[n_, k_, r_] := r*Binomial[(k - 1)*n + r, n]/((k - 1)*n + r);

%t T[n_, k_] := (u[n, k, 1] + If[OddQ[n], u[(n - 1)/2, k, Quotient[k, 2]], If[OddQ[k], (u[n/2 - 1, k, k - 1] + u[n/2, k, 1])/2, u[n/2, k, 1]]] + (If[EvenQ[n], u[n/2, k, 1]] - u[n, k, 2])/2 + DivisorSum[GCD[n - 1, k], EulerPhi[#]*u[(n - 1)/#, k, k/#] &]/k)/2 /. Null -> 0;

%t Table[T[n - k + 2, k + 1], {n, 1, 11}, {k, n + 1, 2, -1}] // Flatten (* _Jean-François Alcover_, Dec 28 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) = {(u(n,k,1) + if(n%2, u((n-1)/2,k,k\2), if(k%2, (u(n/2-1,k,(k-1)) + u(n/2,k,1))/2, u(n/2,k,1))) + (if(n%2==0, u(n/2,k,1))-u(n,k,2))/2 + sumdiv(gcd(n-1,k), d, eulerphi(d)*u((n-1)/d,k,k/d))/k)/2}

%o for(n=1, 10, for(k=3, 8, print1(T(n, k), ", ")); print);

%Y Columns k=3..7 are A000207, A005036, A005040, A004127, A005419.

%Y Cf. A033282, A295222, A295259.

%Y Polyominoes: A295224 (oriented), A070914 (rooted).

%K nonn,tabl

%O 1,9

%A _Andrew Howroyd_, Nov 18 2017