A334247 -id:A334247 - 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.

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

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

Original entry on oeis.org

1, 1, 3, 54, 511863, 12284402192625939

Offset: 0

Matthew Scroggs, Apr 20 2020

a(n) is the number of acyclic orientations of the edges of an n-dimensional cube, with rotations and reflections of the same orientation not counted.

Except for n=0 and n=2, a(n) can be obtained by substituting -1 for x in the chromatic polynomials given in A334358. This fails for n = 2 because the square when folded diagonally gives a graph with an odd number of vertices. The contribution from this graph needs to be negated when determining the number of acyclic orientations. - Andrew Howroyd, Apr 24 2020

Matthew Scroggs, Python code to calculate A334248.
Mathematics Stack Exchange, Combinatorial problem: Directed Acyclic Graph.
Eric Weisstein's World of Mathematics, Hypercube Graph.
Wikipedia, Acyclic orientation.

Cf. A333418. A334247 is the number of acyclic orientations with rotations and reflections of the same orientation included.

Cf. A334358.

a(n) = Sum_{k=1..2^n} (-1)^k * A334358(n, 2^n-k)/(n!*2^n) for n >= 3. - Andrew Howroyd, Apr 24 2020

a(5) from Andrew Howroyd, Apr 24 2020

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Original entry on oeis.org

204, 1862, 14700, 109334, 790524, 5633222, 39828300, 280376054, 1968934044, 13807724582, 96754776300, 677686169174, 4745413960764, 33224340503942, 232596153986700, 1628276158432694, 11398345428510684, 79790067272259302, 558537067986067500, 3909785864202510614

Offset: 3

Peter Kagey, Oct 13 2020

nonn

Conjectured linear recurrence and g.f. confirmed by Kagey's formula. - Ray Chandler, Mar 10 2024

			For n = 4, the 4-prism is the 3-dimensional cube, so a(4) = A334247(3) = 1862.

Peter Kagey, Table of n, a(n) for n = 3..1000
Eric Weisstein's World of Mathematics, Prism Graph
Wikipedia, Acyclic orientation
Index entries for linear recurrences with constant coefficients, signature (14, -63, 106, -56).

Cf. A102080, A124349, A284702.

Cf. A033815 (cross-polytope), A058809 (wheel), A334247 (cube), A338152 (n-demihypercube), A338154 (n-antiprism).

A338153[n_] := 5 + 7^n - 2^(n + 1) - 2*4^n (* Peter Kagey, Nov 15 2020 *)

Conjectures from Colin Barker, Oct 13 2020: (Start)
G.f.: 2*x^3*(102 - 497*x + 742*x^2 - 392*x^3) / ((1 - x)*(1 - 2*x)*(1 - 4*x)*(1 - 7*x)).
a(n) = 14*a(n-1) - 63*a(n-2) + 106*a(n-3) - 56*a(n-4) for n>6.
(End)
a(n) = 5 + 7^n - 2^(n+1) - 2*4^n. - Peter Kagey, Nov 15 2020

A338154 a(n) is the number of acyclic orientations of the edges of the n-antiprism.

Original entry on oeis.org

426, 4968, 50640, 486930, 4547088, 41796168, 380789562, 3451622904, 31194607488, 281440825122, 2536622917920, 22848990484344, 205743704494026, 1852238413383048, 16673036119790640, 150072652217086770, 1350735146332489008, 12157047307392618408

Offset: 3

Peter Kagey, Oct 13 2020

nonn

Conjectured linear recurrence and g.f. confirmed by Kagey's formula. - Ray Chandler, Mar 10 2024

			For n = 3, the 3-antiprism is the octahedron (3-dimensional cross-polytope), so a(3) = A033815(3) = 426.

Peter Kagey, Table of n, a(n) for n = 3..1000
Eric Weisstein's World of Mathematics, Antiprism Graph
Wikipedia, Acyclic orientation
Index entries for linear recurrences with constant coefficients, signature (17, -88, 153, -81).

Cf. A077263, A124352, A124353, A192742, A284699, A284700, A284701, A287988, A294152, A297384.

Cf. A033815 (cross-polytope), A058809 (wheel), A334247 (hypercube), A338152 (demihypercube), A338153 (prism).

A338154[n_] := Round[-2^(1-n)*((7 - Sqrt[13])^n + (7 + Sqrt[13])^n) + 9^n + 5] (* Peter Kagey, Nov 15 2020 *)

Conjectures from Colin Barker, Oct 13 2020: (Start)
G.f.: 6*x^3*(71 - 379*x + 612*x^2 - 324*x^3) / ((1 - x)*(1 - 9*x)*(1 - 7*x + 9*x^2)).
a(n) = 17*a(n-1) - 88*a(n-2) + 153*a(n-3) - 81*a(n-4) for n>6.
(End)
a(n) = -2^(1-n)*((7-sqrt(13))^n + (7+sqrt(13))^n) + 9^n + 5. - Peter Kagey, Nov 15 2020

A338152 a(n) is the number of acyclic orientations of the edges of an n-dimensional demihypercube.

Original entry on oeis.org

1, 2, 24, 24024, 193270310, 767795414400

Offset: 1

Peter Kagey, Oct 13 2020

Eric Weisstein's World of Mathematics, Halved Cube Graph

Cf. A137888, A290060, A295174, A334280.

Cf. A033815 (cross-polytope), A058809 (wheel), A334247 (hypercube), A338153 (prism), A338154 (antiprism).

Table[Abs[ChromaticPolynomial[GraphData[{"HalvedCube",n}]][-1]],{n,1,6}]

a(n) = |Sum_{k=0..2^(n-1)} (-1)^k * A334280(n, k)|.

A338005 Number of graceful labelings of the n-hypercube graph Q_n.

Original entry on oeis.org

1, 2, 16, 2592, 466308864

Offset: 0

Eric W. Weisstein, Oct 06 2020

a(4) computed by Bert Dobbelaere

Eric Weisstein's World of Mathematics, Graceful Labeling
Eric Weisstein's World of Mathematics, Hypercube Graph

Cf. A334247.

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

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A338153 a(n) is the number of acyclic orientations of the edges of the n-prism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A338154 a(n) is the number of acyclic orientations of the edges of the n-antiprism.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A338152 a(n) is the number of acyclic orientations of the edges of an n-dimensional demihypercube.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A338005 Number of graceful labelings of the n-hypercube graph Q_n.

Views

Author

Keywords

Comments

Links

Crossrefs