A307813 - OEIS

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, 10994560532480, 43979257151488, 175919234809856, 703681771077632, 2814737519738880

(list; graph; refs; listen; history; text; internal format)

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

Andrew Howroyd, Table of n, a(n) for n = 3..1000

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}]