A331755 Number of vertices in a regular drawing of the complete bipartite graph K_{n,n}.

2, 5, 13, 35, 75, 159, 275, 477, 755, 1163, 1659, 2373, 3243, 4429, 5799, 7489, 9467, 11981, 14791, 18275, 22215, 26815, 31847, 37861, 44499, 52213, 60543, 70011, 80347, 92263, 105003, 119557, 135327, 152773, 171275, 191721, 213547, 237953

Offset: 1

Author

N. J. A. Sloane, Feb 02 2020

Keywords

• nonn

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..1000
• Lars Blomberg, Scott R. Shannon, 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.
• Scott R. Shannon, Images of vertices for n=2.
• Scott R. Shannon, Images of vertices for n=3.
• Scott R. Shannon, Images of vertices for n=4.
• Scott R. Shannon, Images of vertices for n=5.
• Scott R. Shannon, Images of vertices for n=6
• Scott R. Shannon, Images of vertices for n=7
• Scott R. Shannon, Images of vertices for n=8
• Scott R. Shannon, Images of vertices for n=9
• Scott R. Shannon, Images of vertices for n=10.
• Scott R. Shannon, Images of vertices for n=12.
• Scott R. Shannon, Images of vertices for n=15.
• Eric Weisstein's World of Mathematics, Complete Bipartite Graph
• Index entries for sequences related to stained glass windows

Crossrefs

Cf. A290131 (regions), A290132 (edges), A333274 (polygons per vertex), A333276, A159065.

For K_n see A007569, A007678, A135563.

Programs

Maple

# Maple code from N. J. A. Sloane, Jul 16 2020
V106i := proc(n) local ans,a,b; ans:=0;
for a from 1 to n-1 do for b from 1 to n-1 do
if igcd(a,b)=1 then ans:=ans + (n-a)*(n-b); fi; od: od: ans; end; # A115004
V106ii := proc(n) local ans,a,b; ans:=0;
for a from 1 to floor(n/2) do for b from 1 to floor(n/2) do
if igcd(a,b)=1 then ans:=ans + (n-2*a)*(n-2*b); fi; od: od: ans; end; # A331761
A331755 := n -> 2*(n+1) + V106i(n+1) - V106ii(n+1);

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]+ 2 n, {n, 1, 40}] (* Vincenzo Librandi, Feb 04 2020 *)

Formula

a(n) = A290132(n) - A290131(n) + 1.

a(n) = A159065(n) + 2*n.

This is column 1 of A331453.

a(n) = (9/(8*Pi^2))*n^4 + O(n^3 log(n)). Asymptotic to (9/(2*Pi^2))*A000537(n-1). [Stéphane Legendre, see A159065.]