A290131 -id:A290131 - cp's OEIS frontend

A331754 A290131/2.

0, 1, 6, 20, 48, 102, 184, 317, 506, 772, 1118, 1593, 2180, 2949, 3882, 5011, 6356, 8013, 9922, 12224, 14854, 17878, 21302, 25301, 29748, 34825, 40470, 46800, 53770, 61658, 70214, 79821, 90316, 101809, 114278, 127911, 142540, 158663, 176010, 194749

Offset: 1

N. J. A. Sloane, Feb 02 2020

nonn

Cf. A290131.

A115004 a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).

Original entry on oeis.org

1, 8, 31, 80, 179, 332, 585, 948, 1463, 2136, 3065, 4216, 5729, 7568, 9797, 12456, 15737, 19520, 24087, 29308, 35315, 42120, 50073, 58920, 69025, 80264, 92871, 106756, 122475, 139528, 158681, 179608, 202529, 227400, 254597, 283784, 315957, 350576, 387977

Offset: 1

N. J. A. Sloane, Feb 23 2006

Also (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a square of grid points with side length n. Diagonal of triangle A320541. - Hugo Pfoertner, Oct 22 2018
From Chai Wah Wu, Aug 18 2021: (Start)
Theorem: a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2*n+2-i)*phi(i).
Proof: Since gcd(n,n) = 1 if and only if n = 1, Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + Sum_{i=1..n, j=1..n, gcd(i,j)=1, (i,j) <> (1,1)} (n+1-i)*(n+1-j)
= n^2 + Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j) + Sum_{j=2..n, i=1..j, gcd(i,j)=1} (n+1-i)*(n+1-j) = n^2 + 2*Sum_{i=2..n, j=1..i, gcd(i,j)=1} (n+1-i)*(n+1-j), i.e., the diagonal is not double-counted.
This is equal to n^2 + 2*Sum_{i=2..n, j is a totative of i} (n+1-i)*(n+1-j). Since Sum_{j is a totative of i} 1 = phi(i) and for i > 1, Sum_{j is a totative of i} j = i*phi(i)/2, the conclusion follows.
Similar argument holds for corresponding formulas for A088658, A114043, A114146, A115005, etc.
(End)

Ray Chandler, Table of n, a(n) for n = 1..1000
M. Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5.
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, JIS 12 (2009) 09.5.5.
R. J. Mathar, Graphical representation among sequences closely related to this one (cf. N. J. A. Sloane, "Families of Essentially Identical Sequences").
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021. (Includes this sequence)
N. J. A. Sloane (in collaboration with Scott R. Shannon), Art and Sequences, Slides of guest lecture in Math 640, Rutgers Univ., Feb 8, 2020. Mentions this sequence.

Cf. A320540, A320541, A320544.
The following eight sequences are all essentially the same. The simplest is the present sequence, A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020
Main diagonal of array in A114999.

A115004 := proc(n)
    local a,b,r ;
    r := 0 ;
    for a from 1 to n do
    for b from 1 to n do
        if igcd(a,b) = 1 then
            r := r+(n+1-a)*(n+1-b);
        end if;
    end do:
    end do:
    r ;
end proc:
seq(A115004(n),n=1..30); # R. J. Mathar, Jul 20 2017

a[n_] := Sum[(n-i+1) (n-j+1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
Array[a, 40] (* Jean-François Alcover, Mar 23 2020 *)

a(n) = n^2 + sum(i=2, n, (n+1-i)*(2*n+2-i)*eulerphi(i)); \\ Michel Marcus, May 08 2024

from math import gcd
def a115004(n):
    r=0
    for a in range(1, n + 1):
        for b in range(1, n + 1):
            if gcd(a, b)==1:
                r+=(n + 1 - a)*(n + 1 - b)
    return r
print([a115004(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 21 2017

from sympy import totient
def A115004(n): return n**2 + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(2,n+1)) # Chai Wah Wu, Aug 15 2021

a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).
As n -> oo, a(n) ~ (3/2)*n^4/Pi^2. This follows from Max Alekseyev's formula in A114043. - N. J. A. Sloane, Jul 03 2020
a(n) = n^2 + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 15 2021

A306302 Number of regions into which a figure made up of a row of n adjacent congruent rectangles is divided upon drawing diagonals of all possible rectangles (a(0)=0 by convention).

Original entry on oeis.org

0, 4, 16, 46, 104, 214, 380, 648, 1028, 1562, 2256, 3208, 4384, 5924, 7792, 10052, 12744, 16060, 19880, 24486, 29748, 35798, 42648, 50648, 59544, 69700, 80992, 93654, 107596, 123374, 140488, 159704, 180696, 203684, 228624, 255892, 285152, 317400, 352096, 389576

Offset: 0

Paarth Jain, Feb 05 2019

nonn

Assuming that the rectangles have vertices at (k,0) and (k,1), k=0..n, the projective map (x,y) -> ((1-y)/(x+1),y/(x+1)) maps their partition to the partition of the right isosceles triangle described by Alekseyev et al. (2015), for which Theorem 13 gives the number of regions, line segments, and intersection points. - Max Alekseyev, Apr 10 2019

The figure is made up of A324042 triangles and A324043 quadrilaterals. - N. J. A. Sloane, Mar 03 2020

Jinyuan Wang, Table of n, a(n) for n = 0..1000
Max Alekseyev, Illustration for n = 3.
M. A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions, SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090.
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.
Robert Israel, Maple program, Feb 07 2019
S. Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
Scott R. Shannon, Colored illustration for T(1,1)
Scott R. Shannon, Colored illustration for T(2,1)
Scott R. Shannon, Colored illustration for T(3,1)
Scott R. Shannon, Colored illustration for T(4,1)
Scott R. Shannon, Colored illustration for T(5,1)
Scott R. Shannon, Colored illustration for T(6,1)
Scott R. Shannon, Colored illustration for T(7,1)
Scott R. Shannon, Colored illustration for T(8,1)
Scott R. Shannon, Colored illustration for T(9,1)
Scott R. Shannon, Colored illustration for T(10,1)
Scott R. Shannon, Colored illustration for T(11,1)
Scott R. Shannon, Colored illustration for T(12,1)
Scott R. Shannon, Colored illustration for T(13,1)
Scott R. Shannon, Colored illustration for T(14,1)
Scott R. Shannon, Colored illustration for T(15,1)
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Index entries for sequences related to stained glass windows

See A331755 for the number of vertices, A331757 for the number of edges.
Cf. A007678, A108914, A114043, A324042, A324043, A333286, A333287, A333288, A334694.
A column of A288187. See A288177 for additional references.
Also a column of A331452 and A356790.
The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

# Maple from N. J. A. Sloane, Mar 04 2020, starting at n=1:  First define z(n) = A115004
z := proc(n)
    local a, b, r ;
    r := 0 ;
    for a from 1 to n do
    for b from 1 to n do
        if igcd(a, b) = 1 then
            r := r+(n+1-a)*(n+1-b);
        end if;
    end do:
    end do:
    r ;
end proc:
a := n-> z(n)+n^2+2*n;
[seq(a(n), n=1..50)];

z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[0] = 0;
a[n_] := z[n] + n^2 + 2n;
a /@ Range[0, 40] (* Jean-François Alcover, Mar 24 2020 *)

from sympy import totient
def A306302(n): return 2*n*(n+1) + sum(totient(i)*(n+1-i)*(2*n+2-i) for i in range(2,n+1)) # Chai Wah Wu, Aug 16 2021

a(n) = n + (A114043(n+1) - 1)/2, conjectured by N. J. A. Sloane, Feb 07 2019; proved by Max Alekseyev, Apr 10 2019
a(n) = n + A115005(n+1) = n + A141255(n+1)/2. - Max Alekseyev, Apr 10 2019
a(n) = A324042(n) + A324043(n). - Jinyuan Wang, Mar 19 2020
a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j) + n^2 + 2*n. - N. J. A. Sloane, Apr 11 2020
a(n) = 2n(n+1) + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021

a(6)-a(20) from Robert Israel, Feb 07 2019
Edited and more terms added by Max Alekseyev, Apr 10 2019
a(0) added by N. J. A. Sloane, Feb 04 2020

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

Original entry on oeis.org

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

A114043 Take an n X n square grid of points in the plane; a(n) = number of ways to divide the points into two sets using a straight line.

Original entry on oeis.org

1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303

Offset: 1

Ugo Merlone (merlone(AT)econ.unito.it) and N. J. A. Sloane, Feb 22 2006

Also, half of the number of two-dimensional threshold functions (A114146).
The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696).
The number of ways to divide a (2n) X (2n) grid into two sets of equal size is given by 2*A099957(n). - David Applegate, Feb 23 2006
All terms are odd: the line that misses the grid contributes 1 to the total and all other lines contribute 2, 4 or 8, so the total must be odd.
What can be said about the 3-D generalization? - Max Alekseyev, Feb 27 2006

			Examples: the two sets are indicated by X's and o's.
a(2) = 7:
XX oX Xo XX XX oo oX
XX XX XX Xo oX XX oX
--------------------
a(3) = 29:
XXX oXX ooX ooo ooX ooo
XXX XXX XXX XXX oXX oXX
XXX XXX XXX XXX XXX XXX
-1- -4- -8- -4- -4- -8- Total = 29
--------------------
a(4)= 87:
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo
XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo
--1- --4- --8- --8- --4- --4- --8- --8- --8- --8-
XXXX XXXX XXXX XXXX XXXX
XXXo XXXX XXXX XXXo XXXo
XXoo Xooo oooo Xooo XXoo
Xooo oooo oooo oooo oooo
--4- --8- --2- --4- --8- Total = 87.
--------------------

T. D. Noe, Table of n, a(n) for n = 1..1000
Max A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090. See Eq. (11).
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A114499, A115004, A115005, A116696 (unlabeled case), A114531, A114146.
Cf. A099957.
The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

a[n_] := 2*Sum[(n - i)*(n - j)*Boole[CoprimeQ[i, j]], {i, 1, n - 1}, {j, 1, n - 1}] + 2*n^2 - 2*n + 1; Array[a, 40] (* Jean-François Alcover, Apr 25 2016, after Max Alekseyev *)

from sympy import totient
def A114043(n): return 4*n**2-6*n+3 + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 15 2021

Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j); then a(n+1) = 2*(n^2 + n + V(n,n)) + 1. - Max Alekseyev, Feb 22 2006
a(n) ~ (3/Pi^2) * n^4. - Max Alekseyev, Feb 22 2006
a(n) = A141255(n) + 1. - T. D. Noe, Jun 17 2008
a(n) = 4*n^2 - 6*n + 3 + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021

More terms from Max Alekseyev, Feb 22 2006

A141255 Total number of line segments between points visible to each other in a square n X n lattice.

Original entry on oeis.org

0, 6, 28, 86, 200, 418, 748, 1282, 2040, 3106, 4492, 6394, 8744, 11822, 15556, 20074, 25456, 32086, 39724, 48934, 59456, 71554, 85252, 101250, 119040, 139350, 161932, 187254, 215136, 246690, 280916, 319346, 361328, 407302, 457180, 511714, 570232

Offset: 1

T. D. Noe, Jun 17 2008

nonn

A line segment joins points (a,b) and (c,d) if the points are distinct and gcd(c-a,d-b)=1.

			The 2 x 2 square lattice has a total of 6 line segments: 2 vertical, 2 horizontal and 2 diagonal.

D. M. Acketa, J. D. Zunic: On the number of linear partitions of the (m,n)-grid. Inform. Process. Lett., 38 (3) (1991), 163-168. See Table A.1.
Jovisa Zunic, Note on the number of two-dimensional threshold functions, SIAM J. Discrete Math. Vol. 25 (2011), No. 3, pp. 1266-1268. See Eq. (1.2).

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [From _Seppo Mustonen_, May 13 2010]
Seppo Mustonen, On lines going through a given number of points in a rectangular grid of points [Local copy]
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A141224.

The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

Table[cnt=0; Do[If[GCD[c-a,d-b]<2, cnt++ ], {a,n}, {b,n}, {c,n}, {d,n}]; (cnt-n^2)/2, {n,20}]
(* This recursive code is much more efficient. *)
a[n_]:=a[n]=If[n<=1,0,2*a1[n]-a[n-1]+R1[n]]
a1[n_]:=a1[n]=If[n<=1,0,2*a[n-1]-a1[n-1]+R2[n]]
R1[n_]:=R1[n]=If[n<=1,0,R1[n-1]+4*EulerPhi[n-1]]
R2[n_]:=(n-1)*EulerPhi[n-1]
Table[a[n],{n,1,37}]
(* Seppo Mustonen, May 13 2010 *)
a[n_]:=2 Sum[(n-i) (n-j) Boole[CoprimeQ[i,j]], {i,1,n-1}, {j,1,n-1}] + 2 n^2 - 2 n; Array[a, 40] (* Vincenzo Librandi, Feb 05 2020 *)

from sympy import totient
def A141255(n): return 2*(n-1)*(2*n-1) + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 16 2021

a(n) = A114043(n) - 1.

a(n) = 2*(n-1)*(2n-1) + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 16 2021

A115005 a(n) = (A114043(n) - 1)/2.

Original entry on oeis.org

0, 3, 14, 43, 100, 209, 374, 641, 1020, 1553, 2246, 3197, 4372, 5911, 7778, 10037, 12728, 16043, 19862, 24467, 29728, 35777, 42626, 50625, 59520, 69675, 80966, 93627, 107568, 123345, 140458, 159673, 180664, 203651, 228590, 255857, 285116, 317363, 352058

Offset: 1

N. J. A. Sloane, Feb 23 2006

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

a[n_]:=2 Sum[(n-i) (n-j) Boole[CoprimeQ[i,j]], {i, 1, n-1}, {j, 1, n-1}] / 2 + n^2 - n; Array[a, 40] (* Vincenzo Librandi, Feb 05 2020 *)

from sympy import totient
def A115005(n): return (n-1)*(2*n-1) + sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 15 2021

a(n) = (n-1)*(2n-1) + Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021

Offset corrected by Max Alekseyev, Apr 10 2019

A355798 Number of regions formed in a square by straight line segments when connecting the n-1 points between each corner that divide each edge into n equal parts to the n-1 points on the edge on the opposite side of the square.

Original entry on oeis.org

1, 4, 24, 104, 316, 712, 1588, 2816, 4940, 7672, 12444, 16840, 25968, 34088, 46260, 61048, 82792, 98984, 133032, 156072, 196236, 239048, 298292, 334032, 417072, 483856, 570200, 649816, 786412, 850000, 1037628, 1145424, 1311536, 1485880, 1677660, 1828360, 2158192, 2357376, 2623604, 2852688

Offset: 1

Scott R. Shannon, Jul 17 2022

nonn

Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 4.
Scott R. Shannon, Image for n = 5.
Scott R. Shannon, Image for n = 6.
Scott R. Shannon, Image for n = 7.
Scott R. Shannon, Image for n = 8.
Scott R. Shannon, Image for n = 16.
Scott R. Shannon, Alternative version for n = 15. The lines joining the vertices that are exactly opposite are omitted, forming a more carpet-like image. The number of regions formed, 42224, is less than the sequence version, although more 5,6,7 and 8-gon regions are present.
N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, pp. 20-21.

Cf. A355799 (vertices), A355800 (edges), A355801 (k-gons), A255011 (all vertices), A290131, A331452, A335678.

a(n) = A355800(n) - A355799(n) + 1 by Euler's formula.

A088658 Number of triangles in an n X n unit grid that have minimal possible area (of 1/2).

Original entry on oeis.org

0, 4, 32, 124, 320, 716, 1328, 2340, 3792, 5852, 8544, 12260, 16864, 22916, 30272, 39188, 49824, 62948, 78080, 96348, 117232, 141260, 168480, 200292, 235680, 276100, 321056, 371484, 427024, 489900, 558112, 634724, 718432, 810116, 909600, 1018388, 1135136, 1263828, 1402304, 1551908

Offset: 1

Yuval Dekel (dekelyuval(AT)hotmail.com), Nov 21 2003

nonn

			a(2)=4 because 4 (isosceles right) triangles with area 1/2 can be placed on a 2 X 2 grid.

Ray Chandler, Table of n, a(n) for n = 1..1000
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A045996.

The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
a[n_] := 4 z[n - 1];
Array[a, 40] (* Jean-François Alcover, Mar 24 2020 *)

from sympy import totient
def A088658(n): return 4*(n-1)**2 + 4*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # Chai Wah Wu, Aug 15 2021

a(n+1) = 4*A115004(n).

a(n) = 4*(n-1)^2 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021

a(7)-a(28) from Ray Chandler, May 03 2011

Corrected and extended by Ray Chandler, May 18 2011

A114146 Number of threshold functions on n X n grid.

Original entry on oeis.org

1, 2, 14, 58, 174, 402, 838, 1498, 2566, 4082, 6214, 8986, 12790, 17490, 23646, 31114, 40150, 50914, 64174, 79450, 97870, 118914, 143110, 170506, 202502, 238082, 278702, 323866, 374510, 430274, 493382, 561834, 638694, 722658, 814606, 914362, 1023430, 1140466

Offset: 0

N. J. A. Sloane, Feb 22 2006

nonn

Also, number of intersections of a halfspace with an n X n grid. While A114043 counts cuts, this sequence counts sides of cuts. The only difference between this and twice A114043 is that this makes sense for the empty grid. This is the "labeled" version - rotations and reflections are not taken into account. - David Applegate, Feb 24 2006

In the terminology of Koplowitz et al., this is the number of linear dichotomies on a square grid. - N. J. A. Sloane, Mar 14 2020

Chai Wah Wu, Table of n, a(n) for n = 0..10000
M. A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
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.
Jack Koplowitz, Michael Lindenbaum and A. Bruckstein, The number of digital straight lines on an N*N grid, IEEE Transactions on Information Theory 36.1 (1990): 192-197. See D(n).
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)

Cf. A114043, A114531.

The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4*z(n-1); A114043(n) = 2*z(n-1)+2*n^2-2*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n-1)+n*(n-1); A141255(n) = 2*z(n-1)+2*n*(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2*n. - N. J. A. Sloane, Feb 04 2020

a[0] = 1; a[n_] := 4 Sum[(n-i)(n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 4 n^2 - 4 n + 2;
Array[a, 38, 0] (* Jean-François Alcover, Sep 04 2018, after Max Alekseyev in A114043 *)

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

For n>0, a(n) = 2*A114043(n).

For n>0, a(n) = 8*n^2 - 12*n + 6 + 4*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - Chai Wah Wu, Aug 15 2021

Definition corrected by Max Alekseyev, Oct 23 2008

a(0)=1 prepended by Max Alekseyev, Jan 23 2015

cp's OEIS Frontend

A331754 A290131/2.

Views

Author

Keywords

Crossrefs

A115004 a(n) = Sum_{i=1..n, j=1..n, gcd(i,j)=1} (n+1-i)*(n+1-j).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Python

Formula

A306302 Number of regions into which a figure made up of a row of n adjacent congruent rectangles is divided upon drawing diagonals of all possible rectangles (a(0)=0 by convention).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

Python

Formula

Extensions

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

A114043 Take an n X n square grid of points in the plane; a(n) = number of ways to divide the points into two sets using a straight line.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A141255 Total number of line segments between points visible to each other in a square n X n lattice.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Python

Formula

A115005 a(n) = (A114043(n) - 1)/2.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions