A158348 -id:A158348 - cp's OEIS frontend

A334159 Irregular triangle read by rows: T(n,k) is the number of colorings of the n-hypercube graph using exactly k unlabeled colors, k = 1..2^n.

1, 0, 1, 0, 1, 2, 1, 0, 1, 18, 92, 146, 80, 16, 1, 0, 1, 494, 54583, 1507094, 12630906, 40096740, 58031885, 43419502, 18212138, 4498756, 670366, 60220, 3156, 88, 1, 0, 1, 197546, 5427041958, 17973998149410, 10961517110194516, 1450479305675145412, 56507865332978414188

Offset: 0

Andrew Howroyd, Apr 21 2020

			Triangle begins:
0 | 1;
1 | 0, 1;
2 | 0, 1, 2, 1;
3 | 0, 1, 18, 92, 146, 80, 16, 1;
4 | 0, 1, 494, 54583, 1507094, 12630906, 40096740, 58031885, 43419502, 18212138, 4498756, 670366, 60220, 3156, 88, 1;

Andrew Howroyd, Table of n, a(n) for n = 0..62 (rows 0..5)
Andrew Howroyd, Chromatic Polynomials of Hypercubes Q_0 to Q_5
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A091940, A140986, A158348, A296914, A295176, A334247.

A334247 Number of acyclic orientations of the edges of an n-dimensional cube.

Original entry on oeis.org

1, 2, 14, 1862, 193270310, 47171704165698393638

Offset: 0

Matthew Scroggs, Apr 20 2020

a(n) is the absolute value of the chromatic polynomial of the n-hypercube graph evaluated at -1.

			For n=2, there are 14 ways to orient the edges of a square without cycles (see links).

David Eppstein, 14 acyclic orientations of a square
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A334248 is the number of acyclic orientations with rotations and reflections of the same orientation excluded.
Cf. A140986, A158348, A296914, A334159, A334278.
Cf. A033815 (cross-polytope), A058809 (wheel), A338152 (demihypercube), A338153 (prism), A338154 (antiprism).

with(GraphTheory): with(SpecialGraphs):
a:= n-> abs(ChromaticPolynomial(HypercubeGraph(n), -1)):
seq(a(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

a(n) = Sum_{k=1..2^n} (-1)^(2^n-k) * k! * A334159(n, k). - Andrew Howroyd, Apr 21 2020

a(n) = |Sum_{k=0..2^n} (-1)^k * A334278(n, k)|. - Peter Kagey, Oct 13 2020

a(5) from Andrew Howroyd, Apr 23 2020

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.

Original entry on oeis.org

0, 1, 0, -1, 1, 0, -3, 6, -4, 1, 0, -133, 423, -572, 441, -214, 66, -12, 1, 0, -3040575, 14412776, -31680240, 43389646, -41821924, 30276984, -17100952, 7701952, -2794896, 818036, -191600, 35264, -4936, 496, -32, 1

Offset: 0

Peter Kagey, Apr 21 2020

The sums of the absolute values of the entries in each row gives A334247, the number of acyclic orientations of edges of the n-cube.

			Table begins:
n/k| 0     1    2     3    4     5   6    7  8
---+-------------------------------------------
  0| 0,    1
  1| 0,   -1,   1
  2| 0,   -3,   6,   -4,   1
  3| 0, -133, 423, -572, 441, -214, 66, -12, 1

Peter Kagey, Table of n, a(n) for n = 0..68 (rows 0..5; row 5 from Andrew Howroyd's file)
Andrew Howroyd, Chromatic Polynomials of Hypercubes Q_0 to Q_5
Eric Weisstein's World of Mathematics, Chromatic Polynomial.
Eric Weisstein's World of Mathematics, Hypercube Graph.

Cf. A296914 is the reverse of row 3.
Cf. A334279 is analogous for the n-dimensional cross-polytope, the dual of the n-cube.
Cf. A001787, A002378, A091940, A140986, A158348.
Cf. A334159, A334247, A334358.

with(GraphTheory): with(SpecialGraphs):
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(
    ChromaticPolynomial(HypercubeGraph(n), x)):
seq(T(n), n=0..4);  # Alois P. Heinz, Jan 14 2025

T[n_, k_] := Coefficient[ChromaticPolynomial[HypercubeGraph[n], x], x, k]

T(n,0) = 0.

T(n,k) = Sum_{i=1..2^n}, Stirling1(i,k) * A334159(n,i). - Andrew Howroyd, Apr 25 2020

A334357 Number of nonequivalent proper colorings of the vertices of a 4D hypercube using at most n colors up to rotations and reflections of the cube.

Original entry on oeis.org

0, 1, 72, 7173, 610160, 28654530, 723903411, 11151501102, 117740542158, 928786063095, 5822688352360, 30338870238171, 135818642249082, 535712216425568, 1898338161488055, 6136965479845740, 18323823959847156, 51039512178104637, 133722394132080528

Offset: 1

Andrew Howroyd, Apr 24 2020

Adjacent vertices may not have the same color.

a(n) is the number of nonequivalent n-colorings of the tesseract graph up to graph isomorphism.

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Tesseract Graph
Eric Weisstein's World of Mathematics, Vertex Coloring
Index entries for linear recurrences with constant coefficients, signature (17,-136,680,-2380,6188,-12376,19448,-24310,24310,-19448,12376,-6188,2380,-680,136,-17,1).

Cf. A128767, A158348, A334356, A334358.

a(n) = n*(n - 1)*(n^14 - 31*n^13 + 465*n^12 - 4471*n^11 + 30805*n^10 - 161035*n^9 + 659293*n^8 - 2149343*n^7 + 5610000*n^6 - 11666144*n^5 + 19009100*n^4 - 23485632*n^3 + 20729104*n^2 - 11646800*n + 3125472)/384.

a(n) = Sum_{k=1..16} n^k * A334358(4,16-k) / 384.

A380589 Number of n-colorings of the Hypercube Graph Q5.

Original entry on oeis.org

0, 0, 2, 1185282, 130253748108, 2157531034816940, 7905235551766437150, 7365707045872206479742, 2337101560809838105414712, 327425229254999498091796728, 24489214732779742874109277530, 1119349138930999380736025706650, 34471067091433681765512048700932

Offset: 0

Alois P. Heinz, Jan 27 2025

The Hypercube Graph Q5 has 32 vertices and 80 edges.

All terms are even.

Alois P. Heinz, Table of n, a(n) for n = 0..10000
Eric Weisstein's World of Mathematics, Hypercube Graph
Eric Weisstein's World of Mathematics, Chromatic Polynomial
Index entries for linear recurrences with constant coefficients, signature (33, -528, 5456, -40920, 237336, -1107568, 4272048, -13884156, 38567100, -92561040, 193536720, -354817320, 573166440, -818809200, 1037158320, -1166803110, 1166803110, -1037158320, 818809200, -573166440, 354817320, -193536720, 92561040, -38567100, 13884156, -4272048, 1107568, -237336, 40920, -5456, 528, -33, 1).

Column k=5 of A342128.

Cf. A001477, A002378, A091940, A140986, A158348, A334278.

a:= n-> (((((((((((((((((((((((((((((((n-80)*n+3160)*n-82080)*n+1575420)*n
    -23805776)*n+294640000)*n-3068289720)*n+27406254870)*n-212981036784)*n
    +1455643449120)*n-8822129447280)*n+47712047044920)*n-231347639674200)*n
    +1009138022379076)*n-3968583456247214)*n+14086095737441185)*n-45124968898112160)*n
    +130327084318442384)*n-338572422663483544)*n+788328935798745052)*n
    -1636781898149840504)*n+3009654466362869780)*n-4856773984500880124)*n
    +6797172300402030636)*n-8122089299204814072)*n+8114599308192145448)*n
    -6584797184952049568)*n+4160914137061367054)*n-1915734714629493936)*n
    +569711421560808713)*n-81768640551939777)*n:
seq(a(n), n=0..12);

a(n) = n^32 - 80*n^31 + 3160*n^30 - ... (see Maple program).

A159191 Number of n-colorings of the Robertson graph.

Original entry on oeis.org

0, 0, 0, 24, 3490848, 3501104400, 564523119840, 31643453033640, 886834653776064, 15220684846368288, 181298924180884800, 1627952400490177080, 11672280987833510880, 69664869701930893104, 357038627052783076128, 1609181428647593728200, 6498071673405936462720

Offset: 0

Alois P. Heinz, Apr 05 2009

The Robertson graph is the unique (4,5) cage: the quartic graph on 19 vertices (so 38 edges) with girth 5.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Timme, Marc; van Bussel, Frank; Fliegner, Denny; Stolzenberg, Sebastian (2009) "Counting complex disordered states by efficient pattern matching: chromatic polynomials and Potts partition functions", New J. Phys. 11 023001, doi: 10.1088/1367-2630/11/2/023001.
Weisstein, Eric W. "Robertson Graph".
Weisstein, Eric W. "Chromatic Polynomial".
Index entries for linear recurrences with constant coefficients, signature (20, -190, 1140, -4845, 15504, -38760, 77520, -125970, 167960, -184756, 167960, -125970, 77520, -38760, 15504, -4845, 1140, -190, 20, -1).

The adjacency lists of the Robertson graph are included in A184945.

Cf. A115400, A140986, A157959, A157991, A157992, A157993, A158343, A158344, A158346, A158347, A158348, A158726, A158760, A158792, A158904, A159042, A159055, A159056, A159192, A159299, A166964, A173705, A173710.

a:= n-> n^19 -38*n^18 +703*n^17 -8436*n^16 +73761*n^15 -500004*n^14 +2727105*n^13 -12246808*n^12 +45913333*n^11 -144701057*n^10 +383839223*n^9 -853388854*n^8 +1574465385*n^7 -2370057775*n^6 +2835163369*n^5 -2587310804*n^4 +1685281636*n^3 -693467820*n^2 +134217080*n:
seq(a(n), n=0..20);

a(n) = n^19 -38*n^18 + ... (see Maple program).

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.

Original entry on oeis.org

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.

cp's OEIS Frontend

A334159 Irregular triangle read by rows: T(n,k) is the number of colorings of the n-hypercube graph using exactly k unlabeled colors, k = 1..2^n.

Views

Author

Keywords

Examples

Links

Crossrefs

A334247 Number of acyclic orientations of the edges of an n-dimensional cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Extensions

A334278 Irregular table read by rows: T(n, k) is the coefficient of x^k in the chromatic polynomial of the cubical graph Q_n, 0 <= k <= 2^n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334357 Number of nonequivalent proper colorings of the vertices of a 4D hypercube using at most n colors up to rotations and reflections of the cube.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A380589 Number of n-colorings of the Hypercube Graph Q5.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

A159191 Number of n-colorings of the Robertson graph.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Formula

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