A295224 - OEIS

A295224

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

%I #22 Jan 28 2024 09:21:11

%S 1,1,1,1,1,1,1,1,2,4,1,1,2,7,6,1,1,3,12,25,19,1,1,3,19,57,108,49,1,1,

%T 4,26,118,366,492,150,1,1,4,35,203,931,2340,2431,442,1,1,5,46,332,

%U 1989,7756,16252,12371,1424,1,1,5,57,494,3766,20254,68685,115940,65169,4522

%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 (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 oriented 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 oriented polyominoes, chiral pairs are counted as two. 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="/A295224/b295224.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)/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 | 4 7 12 19 26 35 ...

%e 5 | 6 25 57 118 203 332 ...

%e 6 | 19 108 366 931 1989 3766 ...

%e 7 | 49 492 2340 7756 20254 45448 ...

%e 8 | 150 2431 16252 68685 219388 580203 ...

%e 9 | 442 12371 115940 630465 2459730 7684881 ...

%e 10 | 1424 65169 854981 5966610 28431861 104898024 ...

%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[EvenQ[n], u[n/2, k, 1], 0] - u[n, k, 2])/2 + DivisorSum[GCD[n - 1, k], EulerPhi[#]*u[(n - 1)/#, k, k/#]&]/k;

%t Table[T[n - k + 1, k], {n, 1, 13}, {k, n, 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) = u(n,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;

%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 u(n, k, 1) + ((u(n//2, k, 1) if n%2==0 else 0) - u(n, k, 2))//2 + 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 code

%Y Columns k=3..6 are A001683(n+2), A005034, A005038, A221184(n-1).

%Y Cf. A033282, A070914, A295222, A295259, A295260.

%Y Polyominoes: A295260 (unoriented), A070914 (rooted).

%K nonn,tabl

%O 1,9

%A _Andrew Howroyd_, Nov 17 2017