A159065 Number of crossings in a regular drawing of the complete bipartite graph K(n,n).
0, 1, 7, 27, 65, 147, 261, 461, 737, 1143, 1637, 2349, 3217, 4401, 5769, 7457, 9433, 11945, 14753, 18235, 22173, 26771, 31801, 37813, 44449, 52161, 60489, 69955, 80289, 92203, 104941, 119493, 135261, 152705, 171205, 191649, 213473, 237877
Offset: 1
Examples
For n = 3 draw vertically 3 points regularly spaced on the right, and 3 points regularly spaced on the left. Join the left and right points by straight lines. These lines cross at c(3) = 7 points.
References
- Umberto Eco, Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.
- Athanasius Kircher (1601-1680). Ars Magna Sciendi, In XII Libros Digesta, qua nova et universali Methodo Per Artificiosum Combinationum contextum de omni re proposita plurimis et prope infinitis rationibus disputari, omniumque summaria quaedam cognitio comparari potest, Amstelodami, Apud Joannem Janssonium a Waesberge, et Viduam Elizei Weyerstraet, 1669, fol., pp. 482 (altra ed.: Amstelodami.(ut supra), 1671).
Links
- N. J. A. Sloane, Table of n, a(n) for n = 1..1000 [First 500 terms from Indranil Ghosh]
- Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
- M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
- S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
- Eric Weisstein's World of Mathematics, Complete Bipartite Graph
Programs
-
Maple
A159065 := proc(n) local a,b,c ; c := 0 ; for a from 1 to n-1 do for b from 1 to n-1 do if igcd(a,b) = 1 then c := c+(n-a)*(n-b) ; if 2*a< n and 2*b < n then c := c-(n-2*a)*(n-2*b) ; end if; end if; end do: end do: c ; end proc: seq(A159065(n),n=1..30); # R. J. Mathar, Jul 20 2017
-
Mathematica
a[n_] := Module[{x, y, s1 = 0, s2 = 0}, For[x = 1, x <= n-1, x++, For[y = 1, y <= n-1, y++, If[GCD[x, y] == 1, s1 += (n-x)*(n-y); If[2*x <= n-1 && 2*y <= n-1, s2 += (n-2*x)*(n-2*y)]]]]; s1-s2]; Table[a[n], {n, 1, 40}] (* Jean-François Alcover, Jan 10 2014, translated from Joerg Arndt's PARI code *) -
PARI
a(n) = { my(s1=0, s2=0); for (x=1, n-1, for (y=1, n-1, if ( gcd(x, y)==1, s1 += (n-x) * (n-y); if ( ( 2*x<=n-1) && (2*y<=n-1), s2 += (n-2*x) * (n-2*y); ); ); ); ); return( s1 - s2 ); } \\ Joerg Arndt, Oct 13 2013 -
Pascal
s1:=0; s2:=0; for a:=1 to n-1 do for b:=1 to n-1 do if gcd(a, b)=1 then begin s1:=s1+(n-a)*(n-b); if (2*a<=n-1) and (2*b<=n-1) then s2:=s2+(n-2*a)*(n-2*b); end; a:=s1-s2; -
Python
from math import gcd def a159065(n): c=0 for a in range(1, n): for b in range(1, n): if gcd(a, b)==1: c+=(n - a)*(n - b) if 2*aIndranil Ghosh, Jul 20 2017 -
Python
from sympy import totient def A159065(n): return n-1 if n <= 2 else 2*n-3+3*sum(totient(i)*(n-i)*i for i in range(2,(n+1)//2)) + sum(totient(i)*(n-i)*(2*n-i) for i in range((n+1)//2,n)) # Chai Wah Wu, Aug 16 2021
Formula
a(n) = Sum((n-a)*(n-b); 1<=a
a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1).
For n > 2: a(n) = A115004(n-1)-(n-2)^2-2*Sum{n=2..floor((n-1)/2)} (n-2i)*(n-i)*phi(i) = 2n-3+3*Sum{n=2..floor((n-1)/2)}(n-i)*i*phi(i) + Sum_{n=floor((n+1)/2)..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021