cp's OEIS Frontend

A159065 Number of crossings in a regular drawing of the complete bipartite graph K(n,n).

%I A159065 #62 Feb 16 2025 08:33:10
%S A159065 0,1,7,27,65,147,261,461,737,1143,1637,2349,3217,4401,5769,7457,9433,
%T A159065 11945,14753,18235,22173,26771,31801,37813,44449,52161,60489,69955,
%U A159065 80289,92203,104941,119493,135261,152705,171205,191649,213473,237877
%N A159065 Number of crossings in a regular drawing of the complete bipartite graph K(n,n).
%D A159065 Umberto Eco, Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.
%D A159065 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).
%H A159065 N. J. A. Sloane, <a href="/A159065/b159065.txt">Table of n, a(n) for n = 1..1000</a> [First 500 terms from Indranil Ghosh]
%H A159065 Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, <a href="http://neilsloane.com/doc/rose_5.pdf">Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids</a>, (2020). Also arXiv:2009.07918.
%H A159065 M. Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths2/griffiths.html">Counting the regions in a regular drawing of K_{n,n}</a>, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
%H A159065 S. Legendre, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Legendre/legendre2.html">The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph</a>, J. Integer Seqs., Vol. 12, 2009.
%H A159065 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CompleteBipartiteGraph.html">Complete Bipartite Graph</a>
%F A159065 a(n) = Sum((n-a)*(n-b); 1<=a<n, 1<=b<n, (a,b)=1) - Sum((n-2*a)*(n-2*b); 1<=2*a<n, 1<=2*b<n, (a,b)=1). a(n) = Sum(f(a,b)-g(a,b); 1<=a<n, 1<=b<n,), f(a,b) the number of irreducible fractions p/q with 1<=p<=a,1<=q<=b, g(a,b) the number of rationals admitting at least one reducible form p/q with 1 <= p <= a, 1 <= q <= b (Philippe Paclet).
%F A159065 a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1).
%F A159065 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
%e A159065 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.
%p A159065 A159065 := proc(n)
%p A159065     local a,b,c ;
%p A159065     c := 0 ;
%p A159065     for a from 1 to n-1 do
%p A159065     for b from 1 to n-1 do
%p A159065         if igcd(a,b) = 1 then
%p A159065             c := c+(n-a)*(n-b) ;
%p A159065             if 2*a< n and 2*b < n then
%p A159065                 c := c-(n-2*a)*(n-2*b) ;
%p A159065             end if;
%p A159065         end if;
%p A159065     end do:
%p A159065     end do:
%p A159065     c ;
%p A159065 end proc:
%p A159065 seq(A159065(n),n=1..30); # _R. J. Mathar_, Jul 20 2017
%t A159065 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 *)
%o A159065 (Pascal)
%o A159065 s1:=0; s2:=0;
%o A159065 for a:=1 to n-1 do
%o A159065    for b:=1 to n-1 do
%o A159065       if gcd(a, b)=1 then
%o A159065       begin
%o A159065          s1:=s1+(n-a)*(n-b);
%o A159065          if (2*a<=n-1) and (2*b<=n-1) then
%o A159065             s2:=s2+(n-2*a)*(n-2*b);
%o A159065       end;
%o A159065 a:=s1-s2;
%o A159065 (PARI)
%o A159065 a(n) = {
%o A159065     my(s1=0, s2=0);
%o A159065     for (x=1, n-1,
%o A159065         for (y=1, n-1,
%o A159065             if ( gcd(x, y)==1,
%o A159065                 s1 += (n-x) * (n-y);
%o A159065                 if ( ( 2*x<=n-1) && (2*y<=n-1),
%o A159065                     s2 += (n-2*x) * (n-2*y); );
%o A159065              );
%o A159065         );
%o A159065     );
%o A159065     return( s1 - s2 );
%o A159065 }
%o A159065 \\ _Joerg Arndt_, Oct 13 2013
%o A159065 (Python)
%o A159065 from math import gcd
%o A159065 def a159065(n):
%o A159065     c=0
%o A159065     for a in range(1, n):
%o A159065         for b in range(1, n):
%o A159065             if gcd(a, b)==1:
%o A159065                 c+=(n - a)*(n - b)
%o A159065                 if 2*a<n and 2*b<n:c-=(n - 2*a)*(n - 2*b)
%o A159065     return c
%o A159065 print([a159065(n) for n in range(1, 51)]) # _Indranil Ghosh_, Jul 20 2017
%o A159065 (Python)
%o A159065 from sympy import totient
%o A159065 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
%Y A159065 Cf. A000537, A115004, A114999, A290131, A331755.
%K A159065 easy,nonn
%O A159065 1,3
%A A159065 _Stéphane Legendre_, Apr 04 2009, Jul 11 2009