A298119 -id:A298119 - cp's OEIS frontend

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

N. J. A. Sloane, May 27 2012

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

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

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.

Rows give A003462, A006239, A006240, A212802.
Main diagonal is A212803.
Cf. A298117, A298119.

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 *)

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

\\ 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

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.

Name clarified by Andrew Howroyd, Jan 12 2018

A298117 Array read by antidiagonals: T(m,n) = number of Eulerian cycles in the torus grid graph C_m X C_n.

Original entry on oeis.org

2, 4, 4, 8, 40, 8, 16, 320, 320, 16, 32, 2368, 8616, 2368, 32, 64, 16832, 207496, 207496, 16832, 64, 128, 116608, 4788808, 15639936, 4788808, 116608, 128, 256, 793088, 108326760, 1116199200, 1116199200, 108326760, 793088, 256

Offset: 1

Andrew Howroyd, Jan 12 2018

			Array begins:
=========================================================================
m\n|  1      2         3           4              5                 6
---|---------------------------------------------------------------------
1  |  2      4         8          16             32                64 ...
2  |  4     40       320        2368          16832            116608 ...
3  |  8    320      8616      207496        4788808         108326760 ...
4  | 16   2368    207496    15639936     1116199200       77643032832 ...
5  | 32  16832   4788808  1116199200   242230440480    50917973008584 ...
6  | 64 116608 108326760 77643032832 50917973008584 32098460087825856 ...
...

Andrew Howroyd, Table of n, a(n) for n = 1..105
Eric Weisstein's World of Mathematics, Eulerian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Rows 2..4 are A298198, A282621, A298197.
Main diagonal is A297385.
Cf. A212801, A298119.

A054759 Number of Eulerian orientations of the n X n square lattice (with wrap-around), i.e., number of arrow configurations on n X n grid that satisfy the square ice rule.

Original entry on oeis.org

4, 18, 148, 2970, 143224, 16448400, 4484823396, 2901094068042, 4448410550095612, 16178049740086515288, 139402641051212392498528, 2849295959501939989625992464, 137950545200232788276834783781648, 15844635835975276495290739119895808472

Offset: 1

Steven Finch, Apr 25 2000

nonn

The n X n square lattice with wrap around is also called the torus grid graph. - Andrew Howroyd, Jan 11 2018

Steven R. Finch, Mathematical Constants, Cambridge, 2003, pp. 412-416.
Computed by Jennifer Henry in Dec. 1998.

E. H. Lieb, Residual entropy of square ice, Phys. Rev. 162 (1967) 162-172.
Steven R. Finch, Lieb's Square Ice Constant [Broken link]
Steven R. Finch, Lieb's Square Ice Constant [From the Wayback machine]
Eric Weisstein's World of Mathematics, Torus Grid Graph

Cf. A118273, A358177. Main diagonal of A298119.

Elliot Lieb proved that lim_{n->oo} a(n)^(1/n^2) = (4/3)^(3/2). See A118273.

a(14) from Brendan McKay, Apr 18 2024

A298201 Number of Eulerian orientations of the torus grid graph C_4 X C_n.

Original entry on oeis.org

32, 114, 548, 2970, 16892, 98466, 583412, 3500970, 21232556, 129930354, 801132452, 4970993658, 31006439132, 194231313474, 1220944803668, 7696445791050, 48625129598732, 307759067766546, 1950657679387652, 12377791111168410, 78613025212107836, 499635602835227874

Offset: 1

Andrew Howroyd, Jan 14 2018

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (15,-77,161,-138,40).

Row 4 of A298119.

Cf. A006240, A298197.

LinearRecurrence[{15, -77, 161, -138, 40}, {32, 114, 548, 2970, 16892}, 22] (* Jean-François Alcover, Sep 21 2019 *)

Vec(2*(16 - 183*x + 651*x^2 - 812*x^3 + 300*x^4)/((1 - x)*(1 - 2*x)*(1 - 5*x)*(1 - 7*x + 4*x^2)) + O(x^25))

a(n) = 15*a(n-1) - 77*a(n-2) + 161*a(n-3) - 138*a(n-4) + 40*a(n-5).

G.f.: 2*x*(16 - 183*x + 651*x^2 - 812*x^3 + 300*x^4)/((1 - x)*(1 - 2*x)*(1 - 5*x)*(1 - 7*x + 4*x^2)).

A372093 Number of Eulerian orientations of the torus grid graph C_5 X C_n.

Original entry on oeis.org

64, 308, 2116, 16892, 143224, 1250228, 11091536, 99371772, 895878604, 8109607248, 73605150496, 669235388612, 6091889767144, 55495316073288, 505799972171296, 4611529143198652, 42053844507644124, 383555932615158068, 3498586905231628036, 31914171636394303392

Offset: 1

Brendan McKay, Apr 18 2024

Brendan McKay, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (24,-219,988,-2407,3181,-2042,292,280,-96).

Row 5 of A298119.

Cf. A298201.

a(n) = 24*a(n-1) - 219*a(n-2) + 988*a(n-3) - 2407*a(n-4) + 3181*a(n-5) - 2042*a(n-6) + 292*a(n-7) + 280*a(n-8) - 96*a(n-9).

Asymptotically, a(n) ~ 2*(5+sqrt(17))^n.

A372094 Number of Eulerian orientations of the torus grid graph C_6 X C_n.

Original entry on oeis.org

128, 858, 8324, 98466, 1250228, 16448400, 220603364, 2995602834, 41048196236, 566597492178, 7869683384900, 109903205061360, 1542297167382164, 21736984452051810, 307535339926640204, 4365796637993895186, 62162535924592508036, 887421840845709378960

Offset: 1

Brendan McKay, Apr 18 2024

nonn

Brendan McKay, Table of n, a(n) for n = 1..100
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (55, -1265, 15974, -121977, 578547, -1629798, 2030265, 2559843, -15001158, 26229897, -19679739, -3755273, 21563768, -20454442, 10081600, -2802792, 410688, -24192).

Row 6 of A298119.

Cf. A298201, A372093.

a(n) = 55*a(n-1) - 1265*a(n-2) + 15974*a(n-3) - 121977*a(n-4) + 578547*a(n-5) - 1629798*a(n-6) + 2030265*a(n-7) + 2559843*a(n-8) - 15001158*a(n-9) + 26229897*a(n-10) - 19679739*a(n-11) - 3755273*a(n-12) + 21563768*a(n-13) - 20454442*a(n-14) + 10081600*a(n-15) - 2802792*a(n-16) + 410688*a(n-17) - 24192*a(n-18)

A358177 Number of Eulerian orientations of a (labeled) 2n-dimensional hypercube graph, Q_2n. Q_2n is also the n-dimensional torus grid graph (C_4)^n.

Original entry on oeis.org

1, 2, 2970, 351135773356461511142023680

Offset: 0

Peter Munn and Zachary DeStefano, Nov 02 2022

An Eulerian orientation of a graph is an orientation of the edges such that every vertex has in-degree equal to out-degree. (C_4)^n denotes the Cartesian product of n cycle graphs on 4 nodes.

			For n = 1, dimension 2n = 2, there are two Eulerian orientations (the cyclic ones). So a(1) = 2.

Mikhail Isaev, Brendan D. McKay, and Rui-Ray Zhang, Correlation between residual entropy and spanning tree entropy of ice-type models on graphs, arXiv:2409.04989 [math.CO], 2024. See p. 24.
A. Schrijver, Bounds on the Number of Eulerian Orientations, Combinatorica, 3 (3--4), (1983), 375-380.
Eric Weisstein's World of Mathematics, Cartesian product of graphs
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A007081, A054759, A298119, A307334, A334553.

a(0) = A007081(2^0) = 1.
a(1) = A334553(1) = 2.
a(2) = A054759(4) = 2970.
Schrijver (1983) provides general bounds on unknown terms of the form (2^(-k) * binomial(2k,k))^(2^(2k)) <= a(k) <= sqrt(binomial(2k,k)^(2^(2k))).
From this we have the specific bounds 2.9*10^25 <= a(3) <= 4.3*10^41 and 1.2*10^164 <= a(4) <= 1.5*10^236.

a(3) added by Brendan McKay, Nov 04 2022

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

Extensions

A298117 Array read by antidiagonals: T(m,n) = number of Eulerian cycles in the torus grid graph C_m X C_n.

Views

Author

Keywords

Examples

Links

Crossrefs

A054759 Number of Eulerian orientations of the n X n square lattice (with wrap-around), i.e., number of arrow configurations on n X n grid that satisfy the square ice rule.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Formula

Extensions

A298201 Number of Eulerian orientations of the torus grid graph C_4 X C_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A372093 Number of Eulerian orientations of the torus grid graph C_5 X C_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A372094 Number of Eulerian orientations of the torus grid graph C_6 X C_n.

Views

Author

Keywords

Links

Crossrefs

Formula

A358177 Number of Eulerian orientations of a (labeled) 2n-dimensional hypercube graph, Q_2n. Q_2n is also the n-dimensional torus grid graph (C_4)^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions