|
%I #20 Jun 06 2022 01:34:31
%S 0,8,56,352,1760,8192,35712,151040,624128,2547712,10311680,41541632,
%T 166846464,668991488,2679603200,10726801408,42925948928,171746263040,
%U 687078899712,2748525314048
%N a(n) = (5/32)*4^n - floor((n^2 + 1)/2)*2^(n - 2).
%C 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.
%C 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).
%H K. Clancy, M. Haythorpe and A. Newcombe, <a href="https://arxiv.org/abs/1901.05155">A survey of graphs with known or bounded crossing numbers</a>, arXiv:1901.05155 [math.CO], 2019.
%H R. B. Eggleton and R. K. Guy, <a href="https://www.ams.org/journals/notices/197008/197008FullIssue.pdf">The Crossing Number of the n-Cube</a>, Notices of the American Mathematical Society 17 (1970), 757. (Abstract only, but 17 Mo).
%H P. Erdös and R. K. Guy, <a href="https://doi.org/10.1080/00029890.1973.11993230">Crossing Number Problems</a>, The American Mathematical Monthly, Vol. 80, No. 1 (1973), 52-58.
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCrossingNumber.html">Graph Crossing Number</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HypercubeGraph.html">Hypercube Graph</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (8,-16,-16,80,-64).
%F a(n) = 5/32*4^n - floor((n^2 + 1)/2)*2^(n - 2).
%F a(n) = 2^(n - 5)*(5*2^n - 4*n^2 + 2 (-1)^n - 2).
%F a(n) = 8*a(n-1) - 16*a(n-2) - 16*a(n-3) + 80*a(n-4) - 64*a(n-5).
%F G.f.: -8*x^4*(-1 + x - 4*x^2 + 4*x^3)/((-1 + 2*x)^3*(-1 + 2*x + 8*x^2)).
%t Table[5/32 4^n - Floor[(n^2 + 1)/2] 2^(n - 2), {n, 3, 20}]
%t Table[2^(n - 5) (5 2^n - 4 n^2 + 2 (-1)^n - 2), {n, 3, 20}]
%t LinearRecurrence[{8, -16, -16, 80, -64}, {0, 8, 56, 352, 1760}, 20]
%t 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]
%K nonn
%O 3,2
%A _Eric W. Weisstein_, Apr 30 2019
|
