A007333 An upper bound on the biplanar crossing number of the complete graph on n nodes.

0, 0, 0, 0, 0, 0, 0, 0, 4, 7, 12, 18, 37, 53, 75, 100, 152, 198, 256, 320, 430, 530, 650, 780, 980, 1165, 1380, 1610, 1939, 2247, 2597, 2968, 3472, 3948, 4480, 5040, 5772, 6468, 7236, 8040, 9060, 10035, 11100, 12210, 13585, 14905, 16335, 17820, 19624, 21362

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

This bound in based on a particular decomposition of K_n (see Owens for details). The actual biplanar crossing number for K_9 is 1 (not 4 as given by this bound). - Sean A. Irvine, Dec 30 2019

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280.
• A. Owens, On the biplanar crossing number, IEEE Trans. Circuit Theory, 18 (1971), 277-280. [Annotated scanned copy]
• Index entries for linear recurrences with constant coefficients, signature (2,-1,0,3,-6,3,0,-3,6,-3,0,1,-2,1).

Crossrefs

Cf. A000241, A028723.

Programs

Mathematica

LinearRecurrence[{2,-1,0,3,-6,3,0,-3,6,-3,0,1,-2,1},{0,0,0,0,0,0,0,0,4,7,12,18,37,53},70] (* Harvey P. Dale, Feb 13 2022 *)

PARI

concat([0,0,0,0,0,0,0,0], Vec(x^9*(4 - x + 2*x^2 + x^3 + x^4) / ((1 - x)^5*(1 + x)^3*(1 + x^2)^3) + O(x^40))) \\ Colin Barker, Feb 02 2020

Formula

a(4*k) = k * (k-1) * (k-2) * (7*k-3) / 6, a(4*k+1) = k * (k-1) * (7*k^2-10*k+4) / 6, a(4*k+2) = k * (k-1) * (7*k^2-3*k-1) / 6, a(4*k+3) = k^2 * (k-1) * (7*k+4) / 6 [from Owens]. - Sean A. Irvine, Dec 30 2019; [typo corrected by Colin Barker, Feb 01 2020]

From Colin Barker, Jan 28 2020: (Start)

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

a(n) = 2*a(n-1) - a(n-2) + 3*a(n-4) - 6*a(n-5) + 3*a(n-6) - 3*a(n-8) + 6*a(n-9) - 3*a(n-10) + a(n-12) - 2*a(n-13) + a(n-14) for n>14.

(End)

Extensions

More terms and title clarified by Sean A. Irvine, Dec 30 2019