A115005 -id:A115005 - cp's OEIS frontend

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

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

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

Original entry on oeis.org

0, 2, 12, 40, 96, 204, 368, 634, 1012, 1544, 2236, 3186, 4360, 5898, 7764, 10022, 12712, 16026, 19844, 24448, 29708, 35756, 42604, 50602, 59496, 69650, 80940, 93600, 107540, 123316, 140428, 159642, 180632, 203618, 228556, 255822, 285080, 317326, 352020, 389498

Offset: 1

R. J. Mathar, Jul 20 2017

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Martin Griffiths, Counting the regions in a regular drawing of K_{n,n}, J. Int. Seq. 13 (2010) # 10.8.5. See Lemma 2 and Table 1.
Stéphane Legendre, The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph, J. Integer Seqs., Vol. 12, 2009.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)
Eric Weisstein's World of Mathematics, Complete Bipartite Graph

Cf. A115004, A159065, A290132, A331754.
For K_n see A007569, A007678, A135563.
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

A290131 := proc(n)
    A115004(n-1)+(n-1)^2 ;
end proc:
seq(A290131(n),n=1..30) ;

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

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
def a(n): return a115004(n - 1) + (n - 1)**2
print([a(n) for n in range(1, 51)]) # Indranil Ghosh, Jul 20 2017, after Maple code

from sympy import totient
def A290131(n): return 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) = A115004(n-1) + (n-1)^2.

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

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

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

A114999 Array read by antidiagonals: T(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j), m>=1, n>=1.

Original entry on oeis.org

1, 3, 3, 6, 8, 6, 10, 16, 16, 10, 15, 26, 31, 26, 15, 21, 39, 50, 50, 39, 21, 28, 54, 75, 80, 75, 54, 28, 36, 72, 103, 120, 120, 103, 72, 36, 45, 92, 137, 164, 179, 164, 137, 92, 45, 55, 115, 175, 218, 244, 244, 218, 175, 115, 55, 66, 140, 218, 278, 324, 332, 324, 278, 218, 140

Offset: 1

N. J. A. Sloane, Feb 23 2006

The corresponding triangle is A320541, counting (1/4) * number of ways to select 3 distinct points forming a triangle of unsigned area = 1/2 from a rectangle of grid points with side lengths j and k, written as triangle T(j,k), j<=k. - Hugo Pfoertner, Oct 22 2018

			The top left corner of the array is:
[1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78]
[3, 8, 16, 26, 39, 54, 72, 92, 115, 140, 168, 198]
[6, 16, 31, 50, 75, 103, 137, 175, 218, 265, 318, 374]
[10, 26, 50, 80, 120, 164, 218, 278, 346, 420, 504, 592]
[15, 39, 75, 120, 179, 244, 324, 413, 514, 623, 747, 877]
[21, 54, 103, 164, 244, 332, 441, 562, 699, 846, 1014, 1190]
[28, 72, 137, 218, 324, 441, 585, 745, 926, 1120, 1342, 1575]
[36, 92, 175, 278, 413, 562, 745, 948, 1178, 1424, 1706, 2002]
[45, 115, 218, 346, 514, 699, 926, 1178, 1463, 1768, 2118, 2485]
[55, 140, 265, 420, 623, 846, 1120, 1424, 1768, 2136, 2559, 3002]
[66, 168, 318, 504, 747, 1014, 1342, 1706, 2118, 2559, 3065, 3595]
[78, 198, 374, 592, 877, 1190, 1575, 2002, 2485, 3002, 3595, 4216]
...

Max A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184

Cf. A114043, A115004 (main diagonal), A115005, A115006, A115007, A320541.

T:=proc(m,n) local t1,i,j; t1:=0; for i from 1 to m do for j from 1 to n do if gcd(i,j)=1 then t1:=t1+(m+1-i)*(n+1-j); fi; od; od; t1; end;

T[m_, n_] := Module[{t1, i, j}, t1 = 0; For[i = 1, i <= m, i++, For[j = 1, j <= n, j++, If[GCD[i, j] == 1 , t1 = t1 + (m+1-i)*(n+1-j)]]]; t1]; Table[T[m-n+1, n], {m, 1, 11}, {n, 1, m}] // Flatten (* Jean-François Alcover, Jan 07 2014, translated from Maple *)

A324043 Number of quadrilateral regions into which a figure made up of a row of n adjacent congruent rectangles is divided upon drawing diagonals of all possible rectangles.

Original entry on oeis.org

0, 2, 14, 34, 90, 154, 288, 462, 742, 1038, 1512, 2074, 2904, 3774, 4892, 6154, 7864, 9662, 12022, 14638, 17786, 20998, 25024, 29402, 34672, 40038, 46310, 53038, 61090, 69454, 79344, 89890, 101792, 113854, 127476, 141866, 158428, 175182, 193760, 213274, 235444, 258182, 283858, 310750, 339986

Offset: 1

Jinyuan Wang, May 01 2019

nonn

A row of n adjacent congruent rectangles can only be divided into triangles (cf. A324042) or quadrilaterals when drawing diagonals. Proof is given in Alekseyev et al. (2015) under the transformation described in A306302.

			For k adjacent congruent rectangles, the number of quadrilateral regions in the j-th rectangle is:
k\j|  1   2   3   4   5   6   7  ...
---+--------------------------------
1  |  0,  0,  0,  0,  0,  0,  0, ...
2  |  1,  1,  0,  0,  0,  0,  0, ...
3  |  3,  8,  3,  0,  0,  0,  0, ...
4  |  5, 12, 12,  5,  0,  0,  0, ...
5  |  7, 22, 32, 22,  7,  0,  0, ...
6  |  9, 28, 40, 40, 28,  9,  0, ...
7  | 11, 38, 58, 74, 58, 38, 11, ...
...
a(4) = 5 + 12 + 12 + 5 = 34.

Chai Wah Wu, Table of n, a(n) for n = 1..10000
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.
Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2021). Also arXiv:2009.07918.
Robert Israel, Maple program.
Jinyuan Wang, Illustration for n = 1, 2, 3, 4, 5.

Cf. A007678, A108914, A114043, A115005, A177719, A306302, A324042, A333286, A333287, A333288.

See Robert Israel link.
There are also Maple programs for both A306302 and A324042. Then a := n -> A306302(n) - A324042(n); # N. J. A. Sloane, Mar 04 2020

Table[Sum[Sum[(Boole[GCD[i, j] == 1] - 2 * Boole[GCD[i, j] == 2]) * (n + 1 - i) * (n + 1 - j), {j, 1, n}], {i, 1, n}] - n^2, {n, 1, 45}] (* Joshua Oliver, Feb 05 2020 *)

{ A324043(n) = sum(i=1, n, sum(j=1, n, ( (gcd(i, j)==1) - 2*(gcd(i,j)==2) ) * (n+1-i) * (n+1-j) )) - n^2; } \\ Max Alekseyev, Jul 08 2019

from sympy import totient
def A324043(n): return 0 if n==1 else -2*(n-1)**2 + sum(totient(i)*(n+1-i)*(7*i-2*n-2) 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)) # Chai Wah Wu, Aug 16 2021

a(n) = A115005(n+1) - A177719(n+1) - n - 1 = Sum_{i,j=1..n; gcd(i,j)=1} (n+1-i)*(n+1-j) - 2*Sum_{i,j=1..n; gcd(i,j)=2} (n+1-i)*(n+1-j) - n^2. - Max Alekseyev, Jul 08 2019
a(n) = A306302(n) - A324042(n).
For n>1, a(n) = -2(n-1)^2 + Sum_{i=2..floor(n/2)} (n+1-i)*(7i-2n-2)*phi(i) + Sum_{i=floor(n/2)+1..n} (n+1-i)*(2n+2-i)*phi(i). - Chai Wah Wu, Aug 16 2021

a(8)-a(23) from Robert Israel, Jul 07 2019

Terms a(24) onward from Max Alekseyev, Jul 08 2019

A115009 Array read by antidiagonals: let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)(n+1-j), then T(m,n) = 2mn+m+n+2V(m,n), for m >= 0, n >= 0.

Original entry on oeis.org

0, 1, 1, 2, 6, 2, 3, 13, 13, 3, 4, 22, 28, 22, 4, 5, 33, 49, 49, 33, 5, 6, 46, 74, 86, 74, 46, 6, 7, 61, 105, 131, 131, 105, 61, 7, 8, 78, 140, 188, 200, 188, 140, 78, 8, 9, 97, 181, 251, 289, 289, 251, 181, 97, 9, 10, 118, 226, 326, 386, 418, 386, 326, 226, 118, 10, 11, 141, 277

Offset: 0

N. J. A. Sloane, Feb 24 2006

This is the number of linear partitions of an m X n grid.

			The array begins:
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, ...
1, 6, 13, 22, 33, 46, 61, 78, 97, 118, ...
2, 13, 28, 49, 74, 105, 140, 181, 226, 277, ...
3, 22, 49, 86, 131, 188, 251, 326, 409, 502, ...
4, 33, 74, 131, 200, 289, 386, 503, 632, 777, ...
5, 46, 105, 188, 289, 418, 559, 730, 919, 1132, ...
6, 61, 140, 251, 386, 559, 748, 979, 1234, 1521, ...
7, 78, 181, 326, 503, 730, 979, 1282, 1617, 1994, ...
...

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 Equation (1.2).

Max A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184

The second and third rows are A028872 and A358296.
The main diagonal is A141255 = A114043 - 1.
The lower triangle is A332351.
Cf. A114999, A114043, A115004, A115005, A115006, A115007, A115010, A115011.

V:=proc(m,n) local t1,i,j; t1:=0; for i from 1 to m do for j from 1 to n do if gcd(i,j)=1 then t1:=t1+(m+1-i)*(n+1-j); fi; od; od; t1; end; T:=(m,n)->(2*m*n+m+n+2*V(m,n));

V[m_, n_] := Sum[If[GCD[i, j] == 1, (m-i+1)*(n-j+1), 0], {i, 1, m}, {j, 1, n}]; T[m_, n_] := 2*m*n+m+n+2*V[m, n]; Table[T[m-n, n], {m, 0, 11}, {n, 0, m}] // Flatten (* Jean-François Alcover, Jan 08 2014 *)

cp's OEIS Frontend

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

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

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

Python

Python

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A114146 Number of threshold functions on n X n grid.

Views

A115009 Array read by antidiagonals: let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)(n+1-j), then T(m,n) = 2mn+m+n+2V(m,n), for m >= 0, n >= 0.