A298117 -id:A298117 - cp's OEIS frontend

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

4, 8, 8, 16, 18, 16, 32, 44, 44, 32, 64, 114, 148, 114, 64, 128, 308, 548, 548, 308, 128, 256, 858, 2116, 2970, 2116, 858, 256, 512, 2444, 8324, 16892, 16892, 8324, 2444, 512, 1024, 7074, 33028, 98466, 143224, 98466, 33028, 7074

Offset: 1

Andrew Howroyd, Jan 12 2018

In other words, the number of orientations of the m X n torus grid graph in which each vertex has equal indegree and outdegree.

Values are always even since reversing the orientation of each edge will always result in another Eulerian orientation.

			Array begins:
============================================================
m\n|   1    2     3      4        5         6          7
---|--------------------------------------------------------
1  |   4    8    16     32       64       128        256 ...
2  |   8   18    44    114      308       858       2444 ...
3  |  16   44   148    548     2116      8324      33028 ...
4  |  32  114   548   2970    16892     98466     583412 ...
5  |  64  308  2116  16892   143224   1250228   11091536 ...
6  | 128  858  8324  98466  1250228  16448400  220603364 ...
7  | 256 2444 33028 583412 11091536 220603364 4484823396 ...
...

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

Main diagonal is A054759.
Rows 2..5 are 2*A099754, 2*A170938, A298201, A372093, A372094.
Cf. A212801, A298117.

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.

Original entry on oeis.org

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

A298197 Number of Eulerian cycles in the graph C_4 X C_n.

Original entry on oeis.org

16, 2368, 207496, 15639936, 1116199200, 77643032832, 5318859987584, 360460090519552, 24225364155392512, 1617040095771160576, 107318756823774554112, 7087408485751290626048, 466051677657117523779584, 30530955397986792883159040, 1993388935416599069605396480

Offset: 1

Andrew Howroyd, Jan 14 2018

nonn

a(n) is divisible by 2^n.

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Eulerian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (242, -24508, 1377576, -48319952, 1127281504, -18164303168, 206564578176, -1673816120832, 9654475382784, -39144748253184, 108479226544128, -194648732467200, 202715666841600, -92493840384000).

Row 4 of A298117.

Table[1/4 (-4 (12 - 4 Sqrt[5])^n - 4 (12 + 4 Sqrt[5])^n + 2^n (-3 + 3 2^(1 + n) + 3^n + 5^n - 15^n) + 2 (33 - 5 Sqrt[33])^n + 2 (33 + 5 Sqrt[33])^n) + 1/330 (-11 2^n (6 5^n + 5 6^n) + 50 (33 - 5 Sqrt[33])^n + 50 (33 + 5 Sqrt[33])^n) n, {n, 20}] // Expand (* Eric W. Weisstein, Jan 15 2018 *)
LinearRecurrence[{242, -24508, 1377576, -48319952, 1127281504, -18164303168, 206564578176, -1673816120832, 9654475382784, -39144748253184, 108479226544128, -194648732467200, 202715666841600, -92493840384000}, {16, 2368, 207496, 15639936, 1116199200, 77643032832, 5318859987584, 360460090519552, 24225364155392512, 1617040095771160576, 107318756823774554112, 7087408485751290626048, 466051677657117523779584, 30530955397986792883159040}, 20] (* Eric W. Weisstein, Jan 15 2018 *)
CoefficientList[Series[8 (2 - 188 x + 3321 x^2 + 177454 x^3 - 9041760 x^4 + 171251312 x^5 - 1590178736 x^6 + 5597941472 x^7 + 25225706112 x^8 - 343839085056 x^9 + 1466120669184 x^10 - 2913427243008 x^11 + 2262128394240 x^12)/((1 - 2 x) (1 - 4 x) (1 - 6 x) (1 - 10 x)^2 (1 - 12 x)^2 (1 - 30 x) (1 - 24 x + 64 x^2) (1 - 66 x + 264 x^2)^2), {x, 0, 20}], x] (* Eric W. Weisstein, Jan 15 2018 *)

G.f.: 8*x*(2 - 188*x + 3321*x^2 + 177454*x^3 - 9041760*x^4 + 171251312*x^5 - 1590178736*x^6 + 5597941472*x^7 + 25225706112*x^8 - 343839085056*x^9 + 1466120669184*x^10 - 2913427243008*x^11 + 2262128394240*x^12)/((1 - 2*x)*(1 - 4*x)*(1 - 6*x)*(1 - 10*x)^2*(1 - 12*x)^2*(1 - 30*x)*(1 - 24*x + 64*x^2)*(1 - 66*x + 264*x^2)^2).

a(n) = 242*a(n-1) - 24508*a(n-2) + 1377576*a(n-3) - 48319952*a(n-4) + 1127281504*a(n-5) - 18164303168*a(n-6) + 206564578176*a(n-7) - 1673816120832*a(n-8) + 9654475382784*a(n-9) - 39144748253184*a(n-10) + 108479226544128*a(n-11) - 194648732467200*a(n-12) + 202715666841600*a(n-13) - 92493840384000*a(n-14). - Eric W. Weisstein, Jan 15 2018

A282621 Number of Eulerian cycles in the graph C_3 X C_n.

Original entry on oeis.org

8, 320, 8616, 207496, 4788808, 108326760, 2423906696, 53891103656, 1193490502728, 26367062410600, 581618469479176, 12817206071979816, 282280911579925448, 6214413253138283240, 136776355872474130056, 3009909527048881143976, 66229625352973066928968

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, Eulerian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (47, -742, 4796, -13144, 12320).

Row 3 of A298117.

Table[22^n + 1/3 (2^n + 3 2^(1 + 2 n) - 8 5^n - 2^(1 + n) 7^n), {n, 20}] (* Eric W. Weisstein, Jan 15 2018 *)
LinearRecurrence[{47, -742, 4796, -13144, 12320}, {8, 320, 8616, 207496, 4788808}, 20] (* Eric W. Weisstein, Jan 15 2018 *)
CoefficientList[Series[8 (1 - 7 x - 61 x^2 + 202 x^3)/((1 - 2 x) (1 - 4 x) (1 - 5 x) (1 - 14 x) (1 - 22 x)), {x, 0, 20}], x] (* Eric W. Weisstein, Jan 15 2018 *)

Vec(8*(1 - 7*x - 61*x^2 + 202*x^3)/((1 - 2*x)*(1 - 4*x)*(1 - 5*x)*(1 - 14*x)*(1 - 22*x)) + O(x^20))

a(n) = 47*a(n-1) - 742*a(n-2) + 4796*a(n-3) - 13144*a(n-4) + 12320*a(n-5) for n > 5.
G.f.: 8*x*(1 - 7*x - 61*x^2 + 202*x^3)/((1 - 2*x)*(1 - 4*x)*(1 - 5*x)*(1 - 14*x)*(1 - 22*x)).
a(n) = 22^n + (2^n + 3*2^(1 + 2*n) - 8*5^n - 2^(1 + n)*7^n)/3. - Eric W. Weisstein, Jan 15 2018

A297385 Number of Eulerian cycles in the n X n torus grid graph.

Original entry on oeis.org

2, 40, 8616, 15639936, 242230440480, 32098460087825856, 36433115190009846104160

Offset: 1

Eric W. Weisstein, Dec 29 2017

a(3) is also the number of Eulerian cycles in the 3 X 3 rook graph.

a(4) is also the number of Eulerian cycles in the 4-hypercube (tesseract) graph Q_4.

Eric Weisstein's World of Mathematics, Eulerian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph

Main diagonal of A298117.

Cf. A054759, A212803.

a(4)-a(7) from Andrew Howroyd, Jan 12 2018

a(1)-a(2) from Andrew Howroyd, Jan 12 2018

A298198 Number of Eulerian cycles in the graph Cartesian product of C_n and a double edge.

Original entry on oeis.org

4, 40, 320, 2368, 16832, 116608, 793088, 5318656, 35271680, 231786496, 1511653376, 9795518464, 63126683648, 404881506304, 2586017398784, 16456474427392, 104381066510336, 660139718213632, 4163958223142912, 26202468819927040, 164527129801785344

Offset: 1

Andrew Howroyd, Jan 14 2018

nonn

When n = 2 the graph is the Cartesian product of two double edges.

a(n) is divisible by 2^(n + 1).

Andrew Howroyd, Table of n, a(n) for n = 1..500
Eric Weisstein's World of Mathematics, Eulerian Cycle
Index entries for linear recurrences with constant coefficients, signature (14, -60, 72).

Row 2 of A298117.

Vec(4*(1 - 4*x)/((1 - 2*x)*(1 - 6*x)^2) + O(x^30))

a(n) = 14*a(n-1) - 60*a(n-2) + 72*a(n-3) for n > 3.

G.f.: 4*x*(1 - 4*x)/((1 - 2*x)*(1 - 6*x)^2).

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

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

A298197 Number of Eulerian cycles in the graph C_4 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Formula

A282621 Number of Eulerian cycles in the graph C_3 X C_n.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A297385 Number of Eulerian cycles in the n X n torus grid graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A298198 Number of Eulerian cycles in the graph Cartesian product of C_n and a double edge.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula