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.

1, 2, 2970, 351135773356461511142023680

Offset: 0

Author

Peter Munn and Zachary DeStefano, Nov 02 2022

Keywords

• nonn
• hard
• more

Comments

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.

Examples

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

Links

• 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

Crossrefs

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

Formula

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.

Extensions

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