|
| |
|
|
A159065
|
|
Number of crossings in a regular drawing of the complete bipartite graph K(n,n).
|
|
0
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
REFERENCES
| 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).
Eco, U. Foucault's Pendulum. San Diego: Harcourt Brace Jovanovich, p. 473, 1989.
|
|
|
LINKS
| Eric Weisstein's World of Mathematics, Complete Bipartite Graph
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
|
|
|
FORMULA
| 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). a(n) = (9/(8*pi^2))*n^4 + O(n^3 ln(n)).
|
|
|
EXAMPLE
| 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 in c(3) = 7 points.
|
|
|
PROG
| (Other) (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;
|
|
|
CROSSREFS
| Cf. A115004, A114999. Asymptotic to (9/(2*pi^2))*A000537(n-1).
Sequence in context: A015873 A175367 A022271 * A098931 A143690 A007715
Adjacent sequences: A159062 A159063 A159064 * A159066 A159067 A159068
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| Stephane Legendre (legendre(AT)ens.fr), Apr 04 2009, Jul 11 2009
|
| |
|
|
