A212801 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.

1, 1, 1, 1, 4, 1, 1, 13, 13, 1, 1, 40, 108, 40, 1, 1, 121, 793, 793, 121, 1, 1, 364, 5611, 12800, 5611, 364, 1, 1, 1093, 39312, 193721, 193721, 39312, 1093, 1, 1, 3280, 274933, 2886520, 6050000, 2886520, 274933, 3280, 1, 1, 9841, 1923025, 42999713, 183990301, 183990301, 42999713, 1923025, 9841, 1

Offset

1,5

Comments

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

Links

Andrew Howroyd, Table of n, a(n) for n = 1..1275

Germain Kreweras, Complexité et circuits Eulériens dans les sommes tensorielles de graphes, J. Combin. Theory, B 24 (1978), 202-212. See p. 211.

Formula

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.

Example

Array begins:
======================================================================
m\n| 1    2      3        4          5            6              7
---|------------------------------------------------------------------
1  | 1    1      1        1          1            1              1 ...
2  | 1    4     13       40        121          364           1093 ...
3  | 1   13    108      793       5611        39312         274933 ...
4  | 1   40    793    12800     193721      2886520       42999713 ...
5  | 1  121   5611   193721    6050000    183990301     5598183221 ...
6  | 1  364  39312  2886520  183990301  11218701312   681838513861 ...
7  | 1 1093 274933 42999713 5598183221 681838513861 81959473720768 ...
...

Mathematica

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}];
Table[T[m - n + 1, n] // FullSimplify, {m, 1, 10}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jun 30 2018 *)

Prog

(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)));
tabl(nn) = matrix(nn, nn, m, n, round(real(T(m, n)))); \\ Michel Marcus, Feb 01 2016
(PARI) \\ all integer version.
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))}
T(m, n)={my(p=R(n, x->2-x-y)); R(m, x->subst(p, y, x))} \\ Andrew Howroyd, May 19 2020

Crossrefs

Rows give A003462, A006239, A006240, A212802.

Main diagonal is A212803.

Cf. A298117, A298119.

Sequence in context: A146956 A152613 A157153 * A147565 A022167 A339849

Adjacent sequences: A212798 A212799 A212800 * A212802 A212803 A212804

Keyword

nonn,tabl

Author

N. J. A. Sloane, May 27 2012

Extensions

Name clarified by Andrew Howroyd, Jan 12 2018

Status

approved