A307334 -id:A307334 - cp's OEIS frontend

A342128 Table read by antidiagonals upwards: T(n,k) is the number of n-colorings of the vertices of the k-dimensional hypercube such that no two adjacent vertices have the same color. n >= 0, k >=0.

0, 1, 0, 2, 0, 0, 3, 2, 0, 0, 4, 6, 2, 0, 0, 5, 12, 18, 2, 0, 0, 6, 20, 84, 114, 2, 0, 0, 7, 30, 260, 2652, 2970, 2, 0, 0, 8, 42, 630, 29660, 1321860, 1185282, 2, 0, 0, 9, 56, 1302, 198030, 187430900, 130253748108, 100301050602, 2, 0, 0, 10, 72, 2408, 932862, 10199069190, 2157531034816940

Offset: 0

Peter Kagey, Feb 28 2021

			Table begins:
  n\k|  0   1     2         3                4                              5
  ---+-----------------------------------------------------------------------
   0 |  0   0     0         0                0                              0
   1 |  1   0     0         0                0                              0
   2 |  2   2     2         2                2                              2
   3 |  3   6    18       114             2970                        1185282
   4 |  4  12    84      2652          1321860                   130253748108
   5 |  5  20   260     29660        187430900               2157531034816940
   6 |  6  30   630    198030      10199069190            7905235551766437150
   7 |  7  42  1302    932862     269591166222         7365707045872206479742
   8 |  8  56  2408   3440024    4221404762120      2337101560809838105414712
   9 |  9  72  4104  10599192   44876701584360    327425229254999498091796728
  10 | 10  90  6570  28478970  355148098691850  24489214732779742874109277530

Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hypercube Graph

Columns and rows: A002378 (k=1), A091940 (k=2), A140986 (k=3), A158348 (k=4), A380589 (k=5), A307334 (n=3).

Cf. A334278, A342088 (analogous for cross-polytope).

T(n,k) = Sum_{i=0..2^k} A334278(k,i)*n^i.

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

A375346 Number of orientations of the uniform Lagrangian matroid on n elements.

Original entry on oeis.org

1, 6, 38, 990, 395094, 33433683534

Offset: 1

Jesse Selover, Aug 12 2024

a(n) is the number of functions F from the powerset of {1, ..., n} to {-1, +1} with F(empty set) = +1 and satisfying the constraint: F({i} union S) != F({j} union S) => F(S) != F({i,j} union S) for any subset S and distinct i,j not in S.

Tobias Boege, Jesse Selover, and Maksym Zubkov, Sign patterns of principal minors of real symmetric matrices, arXiv:2407.17826 [math.CO], 2024-2025 (see also code and data). See Table 2 on p. 10.
Richard F. Booth, Alexandre V. Borovik, Israel M. Gelfand, and Neil White, Oriented Lagrangian Matroids, European Journal of Combinatorics, 22(5) (2001), 639-656.

Cf. A307334.

a(n) = (1/3) * A307334(n) for n >= 2. - Tobias Boege, Jan 22 2025

a(6) from Tobias Boege, Jan 22 2025

cp's OEIS Frontend

A342128 Table read by antidiagonals upwards: T(n,k) is the number of n-colorings of the vertices of the k-dimensional hypercube such that no two adjacent vertices have the same color. n >= 0, k >=0.

Views

Author

Keywords

Examples

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

A375346 Number of orientations of the uniform Lagrangian matroid on n elements.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions