A331761 -id:A331761 - cp's OEIS frontend

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

N. J. A. Sloane, Feb 02 2020

nonn

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

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

For K_n see A007569, A007678, A135563.

# 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);

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 *)

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.]

A334701 Consider the figure made up of a row of n adjacent congruent rectangles, with diagonals of all possible rectangles drawn; a(n) = number of interior vertices where exactly two lines cross.

Original entry on oeis.org

1, 6, 24, 54, 124, 214, 382, 598, 950, 1334, 1912, 2622, 3624, 4690, 6096, 7686, 9764, 12010, 14866, 18026, 21904, 25918, 30818, 36246, 42654, 49246, 57006, 65334, 75098, 85414, 97384, 110138, 124726, 139642, 156286, 174018, 194106, 214570, 237534, 261666, 288686, 316770, 348048, 380798, 416524, 452794, 492830

Offset: 1

Scott R. Shannon and N. J. A. Sloane, May 30 2020

nonn

It would be nice to have a formula or recurrence. - N. J. A. Sloane, Jun 22 2020

Lars Blomberg, Table of n, a(n) for n = 1..500
Lars Blomberg, Array (s,n) of the number of internal vertices where exactly s=2..501 lines cross in a figure made up of a row of n=1..500 adjacent congruent rectangles, with diagonals of all possible rectangles drawn. Rows are stored comma-separated.
Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
Scott R. Shannon, Colored illustration showing regions for n=1
Scott R. Shannon, Images of vertices for n=1.
Scott R. Shannon, Colored illustration showing regions for n=2
Scott R. Shannon, Images of vertices for n=2.
Scott R. Shannon, Colored illustration showing regions for n=3
Scott R. Shannon, Images of vertices for n=3.
Scott R. Shannon, Colored illustration showing regions for n=4
Scott R. Shannon, Images of vertices for n=4.
Scott R. Shannon, Colored illustration showing regions for n=5
Scott R. Shannon, Images of vertices for n=5
Scott R. Shannon, Colored illustration showing regions for n=6
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=11.
Scott R. Shannon, Images of vertices for n=14.
Index entries for sequences related to stained glass windows

Column 4 of array in A333275.
Cf. A306302, A331755, A290131, A333274.
See also A115004, A331761.

Conjecture: As n -> oo, a(n) ~ C*n^4/Pi^2, where C is about 0.95 (compare A115004, A331761). - N. J. A. Sloane, Jul 03 2020

More terms from Lars Blomberg, Jun 17 2020

A331762 Triangle read by rows: T(n,k) (1 <= k <= n) = Sum_{i=1..n, j=1..k, gcd(i,j)=2} (n+1-i)*(k+1-j).

Original entry on oeis.org

0, 0, 1, 0, 2, 4, 0, 4, 8, 15, 0, 6, 12, 22, 32, 0, 9, 18, 33, 48, 71, 0, 12, 24, 44, 64, 94, 124, 0, 16, 32, 58, 84, 123, 162, 211, 0, 20, 40, 72, 104, 152, 200, 260, 320, 0, 25, 50, 90, 130, 190, 250, 325, 400, 499

Offset: 1

N. J. A. Sloane, Feb 04 2020

			Triangle begins:
  0;
  0,  1;
  0,  2,  4;
  0,  4,  8,  15;
  0,  6, 12,  22,  32;
  0,  9, 18,  33,  48,  71;
  0, 12, 24,  44,  64,  94, 124;
  0, 16, 32,  58,  84, 123, 162, 211;
  0, 20, 40,  72, 104, 152, 200, 260, 320;
  0, 25, 50,  90, 130, 190, 250, 325, 400, 499;
  0, 30, 60, 108, 156, 228, 300, 390, 480, 598, 716;
  ...

M. A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184
M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.

Cf. A115004, A114999, A320541.
The main diagonal is A331761.
See A335683 for another version.

V := proc(m,n,q) local a,i,j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i,j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
for m from 1 to 12 do
lprint([seq(V(m,n,2),n=1..m)]); od:

Table[Sum[Boole[GCD[i, j] == 2] (n + 1 - i) (k + 1 - j), {i, n}, {j, k}], {n, 11}, {k, n}] // Flatten (* Michael De Vlieger, Feb 04 2020 *)

A332596 Number of quadrilateral regions in a "frame" of size n X n (see Comments in A331776 for definition), divided by 8.

Original entry on oeis.org

0, 1, 10, 26, 63, 107, 189, 294, 455, 627, 891, 1202, 1650, 2121, 2719, 3392, 4292, 5239, 6470, 7832, 9463, 11129, 13205, 15460, 18164, 20919, 24130, 27572, 31679, 35945, 40977, 46340, 52384, 58511, 65421, 72718, 81104, 89589, 98989, 108860, 120062, 131551

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 02 2020

nonn

See A331776 for many other illustrations.

Theorem. Let z(n) = Sum_{i, j = 1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) (this is A115004) and z_2(n) = Sum_{i, j = 1..n, gcd(i,j)=2} (n+1-i)*(n+1-j) (this is A331761). Then, for n >= 2, 8*a(n) = 4*z(n) - 8*z_2(n) + 8*n^2 - 36*n + 24. - Scott R. Shannon and N. J. A. Sloane, Mar 06 2020

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Scott R. Shannon, Colored illustration for a(3) = 10 (there are 8*10 quadrilaterals).

Cf. A115004, A331761, A331776, A332594, A332595.

V := proc(m, n, q) local a, i, j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i, j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
f := n -> if n=1 then 0 else 8*n^2 - 36*n + 24 + 4*V(n,n,1) 8*V(n, n, 2); fi;
[seq(f(n)/8, n=1..60)]; # N. J. A. Sloane, Mar 10 2020

a(n) = sum(i=1, n, sum(j=1, n, if(gcd(i, j)==1, (n+1-i)*(n+1-j), 0)))/2 - sum(i=1, n, sum(j=1, n, if(gcd(i, j)==2, (n+1-i)*(n+1-j), 0))) + n^2 - 9*n/2 + 3; \\ Jinyuan Wang, Aug 07 2021

from sympy import totient
def A332596(n): return 0 if n == 1 else ((n-1)*(n-4) - sum(totient(i)*(n+1-i)*(2*n+2-7*i) for i in range(2,n//2+1)) + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(n//2+1,n+1)))//2 # Chai Wah Wu, Aug 16 2021

For n > 1, a(n) = ((n-1)*(n-4) - Sum_{i=2..floor(n/2)} (n+1-i)*(2*n+2-7*i)*phi(i) + Sum_{i=floor(n/2)+1..n} (n+1-i)*(2*n+2-i)*phi(i))/2. - Chai Wah Wu, Aug 16 2021

More terms from N. J. A. Sloane, Mar 10 2020

A332595 Number of triangular regions in a "frame" of size n X n (see Comments in A331776 for definition), divided by 4.

Original entry on oeis.org

1, 12, 32, 72, 128, 232, 368, 576, 832, 1232, 1712, 2328, 3040, 4040, 5184, 6616, 8224, 10248, 12496, 15144, 18048, 21688, 25664, 30184, 35072, 41000, 47392, 54608, 62336, 71088, 80416, 90864, 101952, 114832, 128480, 143352, 159040, 176984, 195888, 216424, 237984, 261624, 286384, 313184, 341184, 372496, 405184

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 02 2020

nonn

See A331776 for many other illustrations.

Theorem. Let z_2(n) = Sum_{i, j = 1..n, gcd(i,j)=2} (n+1-i)*(n+1-j) (this is A331761). Then, for n >= 2, a(n) = 2*(z_2(n) + (n+3)*(n-1)). - Scott R. Shannon and N. J. A. Sloane, Mar 06 2020

Scott R. Shannon, Colored illustration for a(3) = 32 (there are 4*32 triangles).

Cf. A331761, A331776, A332594, A332596.

V := proc(m,n,q) local a,i,j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i,j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
f := n -> if n=1 then 4 else 8*n^2 + 16*n - 24 + 8*V(n,n,2); fi;
[seq(f(n)/4, n=1..60)]; # N. J. A. Sloane, Mar 09 2020

More terms from N. J. A. Sloane, Mar 09 2020

A332597 Number of edges in a "frame" of size n X n (see Comments in A331776 for definition).

Original entry on oeis.org

8, 92, 360, 860, 1792, 3124, 5256, 8188, 12304, 17460, 24568, 33244, 44688, 58228, 74664, 94028, 118080, 145380, 178568, 216252, 259776, 308276, 365352, 428556, 501152, 580804, 670536, 768908, 880992, 1001764, 1138248, 1286748, 1449984, 1625300, 1817752, 2023740, 2252048, 2495476, 2759304, 3040460, 3349056

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 02 2020

nonn

See A331776 for many other illustrations.

Theorem. Let z(n) = Sum_{i, j = 1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) (this is A115004) and z_2(n) = Sum_{i, j = 1..n, gcd(i,j)=2} (n+1-i)*(n+1-j) (this is A331761). Then, for n >= 2, a(n) = 8*z(n) - 4*z_2(n) + 28*n^2 - 44*n + 8. - Scott R. Shannon and N. J. A. Sloane, Mar 06 2020

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Scott R. Shannon, Colored illustration for a(3) = 360 (there are 360 edges in this picture).

Cf. A115004, A331761, A331776 (regions), A332598 (vertices).

V := proc(m, n, q) local a, i, j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i, j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
f := n -> if n=1 then 8 else 28*n^2 - 44*n + 8 + 8*V(n,n,1) - 4*V(n, n, 2); fi;
[seq(f(n), n=1..50)]; # N. J. A. Sloane, Mar 10 2020

from sympy import totient
def A332597(n): return 8 if n == 1 else 4*(n-1)*(8*n-1) + 8*sum(totient(i)*(n+1-i)*(n+i+1) for i in range(2,n//2+1)) + 8*sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(n//2+1,n+1)) # Chai Wah Wu, Aug 16 2021

For n > 1, a(n) = 4*(n-1)*(8*n-1) + 8*Sum_{i=2..floor(n/2)} (n+1-i)*(n+i+1)*phi(i) + 8*Sum_{i=floor(n/2)+1..n} (n+1-i)*(2*n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021

More terms from N. J. A. Sloane, Mar 10 2020

A332598 Number of vertices in a "frame" of size n X n (see Comments in A331776 for definition).

Original entry on oeis.org

5, 27, 152, 364, 776, 1340, 2272, 3532, 5336, 7516, 10592, 14316, 19328, 25100, 32176, 40428, 50848, 62476, 76824, 93020, 111880, 132492, 157056, 184140, 215552, 249452, 287928, 329900, 378216, 429852, 488768, 552572, 623104, 697884, 780464, 868588, 967056

Offset: 1

Scott R. Shannon and N. J. A. Sloane, Mar 02 2020

nonn

See A331776 for many other illustrations.

Theorem. Let z(n) = Sum_{i, j = 1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) (this is A115004) and z_2(n) = Sum_{i, j = 1..n, gcd(i,j)=2} (n+1-i)*(n+1-j) (this is A331761). Then, for n >= 3, a(n) = 4*z(n) - 4*z_2(n) + 12*n^2 - 24*n + 8. (This does not hold for n<3, because it uses Euler's formula, and the graph for n<3 has no hole, so has genus 0, whereas for n>=3 there is a hole and the graph has genus 1.) - Scott R. Shannon and N. J. A. Sloane, Mar 04 2020

Jinyuan Wang, Table of n, a(n) for n = 1..1000
Scott R. Shannon, Colored illustration for a(3) = 152 (there are 152 vertices in this picture).

Cf. A331776 (regions), A332597 (edges).

V := proc(m, n, q) local a, i, j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i, j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
f := n -> if n=1 then 5 elif n=2 then 27 else 12*n^2 - 24*n + 8 + 4*V(n,n,1) - 4*V(n, n, 2); fi;
[seq(f(n), n=1..50)]; # N. J. A. Sloane, Mar 10 2020

a(n) = if(n<3, 22*n - 17, 4*sum(i=1, n, sum(j=1, n, if(gcd(i, j)==1, (n+1-i)*(n+1-j), 0))) - 4*sum(i=1, n, sum(j=1, n, if(gcd(i, j)==2, (n+1-i)*(n+1-j), 0))) + 12*n^2 - 24*n + 8); \\ Jinyuan Wang, Aug 07 2021

from sympy import totient
def A332598(n): return 22*n-17 if n <= 2 else 4*(n-1)*(3*n-1) + 12*sum(totient(i)*(n+1-i)*i for i in range(2,n//2+1)) + 4*sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(n//2+1,n+1)) # Chai Wah Wu, Aug 16 2021

For n > 2, a(n) = 4*(n-1)*(3n-1)+12*Sum_{i=2..floor(n/2)} (n+1-i)*i*phi(i) + 4*Sum_{i=floor(n/2)+1..n} (n+1-i)*(2*n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021

More terms from N. J. A. Sloane, Mar 10 2020

cp's OEIS Frontend

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A334701 Consider the figure made up of a row of n adjacent congruent rectangles, with diagonals of all possible rectangles drawn; a(n) = number of interior vertices where exactly two lines cross.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A331762 Triangle read by rows: T(n,k) (1 <= k <= n) = Sum_{i=1..n, j=1..k, gcd(i,j)=2} (n+1-i)*(k+1-j).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

A332596 Number of quadrilateral regions in a "frame" of size n X n (see Comments in A331776 for definition), divided by 8.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

Extensions

A332595 Number of triangular regions in a "frame" of size n X n (see Comments in A331776 for definition), divided by 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

A332597 Number of edges in a "frame" of size n X n (see Comments in A331776 for definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Python

Formula

Extensions

A332598 Number of vertices in a "frame" of size n X n (see Comments in A331776 for definition).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

PARI

Python

Formula

Extensions