A307813 a(n) = (5/32)*4^n - floor((n^2 + 1)/2)*2^(n - 2).

0, 8, 56, 352, 1760, 8192, 35712, 151040, 624128, 2547712, 10311680, 41541632, 166846464, 668991488, 2679603200, 10726801408, 42925948928, 171746263040, 687078899712, 2748525314048

Offset

3,2

Comments

This was formerly conjectured (by Erdos and Guy, 1973) to be the crossing number of the n-hypercube graph for n >= 3; cr(Q_n) = 0 for n = 0, 1, 2, 3.

Embeddings of Q_n with cr(Q_n) = a(n) are known for n = 5 and 6. However, the Erdos-Guy conjecture is now refuted since cr(Q_7) <= 1744 < a(7) = 1760 (Clancy et al. 2019).

Links

Table of n, a(n) for n=3..22.

K. Clancy, M. Haythorpe and A. Newcombe, A survey of graphs with known or bounded crossing numbers, arXiv:1901.05155 [math.CO], 2019.

R. B. Eggleton and R. K. Guy, The Crossing Number of the n-Cube, Notices of the American Mathematical Society 17 (1970), 757. (Abstract only, but 17 Mo).

P. Erdös and R. K. Guy, Crossing Number Problems, The American Mathematical Monthly, Vol. 80, No. 1 (1973), 52-58.

Eric Weisstein's World of Mathematics, Graph Crossing Number

Eric Weisstein's World of Mathematics, Hypercube Graph

Index entries for linear recurrences with constant coefficients, signature (8,-16,-16,80,-64).

Formula

a(n) = 5/32*4^n - floor((n^2 + 1)/2)*2^(n - 2).

a(n) = 2^(n - 5)*(5*2^n - 4*n^2 + 2 (-1)^n - 2).

a(n) = 8*a(n-1) - 16*a(n-2) - 16*a(n-3) + 80*a(n-4) - 64*a(n-5).

G.f.: -8*x^4*(-1 + x - 4*x^2 + 4*x^3)/((-1 + 2*x)^3*(-1 + 2*x + 8*x^2)).

Mathematica

Table[5/32 4^n - Floor[(n^2 + 1)/2] 2^(n - 2), {n, 3, 20}]
Table[2^(n - 5) (5 2^n - 4 n^2 + 2 (-1)^n - 2), {n, 3, 20}]
LinearRecurrence[{8, -16, -16, 80, -64}, {0, 8, 56, 352, 1760}, 20]
CoefficientList[Series[-8 x (-1 + x - 4 x^2 + 4 x^3)/((-1 + 2 x)^3 (-1 + 2 x + 8 x^2)), {x, 0, 20}], x]

Crossrefs

Sequence in context: A215227 A034006 A334333 * A291387 A272773 A162754

Adjacent sequences: A307810 A307811 A307812 * A307814 A307815 A307816

Keyword

nonn

Author

Eric W. Weisstein, Apr 30 2019

Status

approved