login
Square array read by antidiagonals: T(m,n) = number of Eulerian circuits in the Cartesian product of two directed cycles of lengths m and n.
7

%I #34 May 19 2020 16:18:24

%S 1,1,1,1,4,1,1,13,13,1,1,40,108,40,1,1,121,793,793,121,1,1,364,5611,

%T 12800,5611,364,1,1,1093,39312,193721,193721,39312,1093,1,1,3280,

%U 274933,2886520,6050000,2886520,274933,3280,1,1,9841,1923025,42999713,183990301,183990301,42999713,1923025,9841,1

%N Square array read by antidiagonals: T(m,n) = number of Eulerian circuits in the Cartesian product of two directed cycles of lengths m and n.

%C All rows and columns are given by linear recurrences with constant coefficients. Empirically, the order of the recurrences for n=1..8 appear to be 1, 2, 4, 8, 16, 24, 64, 128. - _Andrew Howroyd_, May 19 2020

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

%H Germain Kreweras, <a href="http://dx.doi.org/10.1016/0095-8956(78)90021-7">Complexité et circuits Eulériens dans les sommes tensorielles de graphes</a>, J. Combin. Theory, B 24 (1978), 202-212. See p. 211.

%F T(m,n) = Product_{k=1..n-1} Product_{h=1..m-1} (2 - exp(2*i*h*Pi/m) - exp(2*i*k*Pi/n)), where i is the imaginary unit.

%e Array begins:

%e ======================================================================

%e m\n| 1 2 3 4 5 6 7

%e ---|------------------------------------------------------------------

%e 1 | 1 1 1 1 1 1 1 ...

%e 2 | 1 4 13 40 121 364 1093 ...

%e 3 | 1 13 108 793 5611 39312 274933 ...

%e 4 | 1 40 793 12800 193721 2886520 42999713 ...

%e 5 | 1 121 5611 193721 6050000 183990301 5598183221 ...

%e 6 | 1 364 39312 2886520 183990301 11218701312 681838513861 ...

%e 7 | 1 1093 274933 42999713 5598183221 681838513861 81959473720768 ...

%e ...

%t T[m_, n_] := Product[2 - Exp[2*I*h*Pi/m] - Exp[2*I*k*Pi/n], {h, 1, m - 1}, {k, 1, n - 1}];

%t Table[T[m - n + 1, n] // FullSimplify, {m, 1, 10}, {n, 1, m}] // Flatten (* _Jean-François Alcover_, Jun 30 2018 *)

%o (PARI) T(m,n) = prod(k=1, n-1, prod(h=1, m-1, 2 - exp(2*I*h*Pi/m) - exp(2*I*k*Pi/n)));

%o tabl(nn) = matrix(nn, nn, m, n, round(real(T(m,n)))); \\ _Michel Marcus_, Feb 01 2016

%o (PARI) \\ all integer version.

%o R(n,f)={my(p=lift(prod(i=1, n-1, f(Mod(x^i, 1-x^n))))); sumdiv(n, d, moebius(n/d) * polcoef(p, d%n, x))}

%o T(m,n)={my(p=R(n, x->2-x-y)); R(m, x->subst(p, y, x))} \\ _Andrew Howroyd_, May 19 2020

%Y Rows give A003462, A006239, A006240, A212802.

%Y Main diagonal is A212803.

%Y Cf. A298117, A298119.

%K nonn,tabl

%O 1,5

%A _N. J. A. Sloane_, May 27 2012

%E Name clarified by _Andrew Howroyd_, Jan 12 2018