A306302 -id:A306302 - cp's OEIS frontend

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

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

A288187 Triangle read by rows: T(n,m) (n >= m >= 1) = number of chambers (or regions) formed by drawing the line segments connecting any two of the (n+1) X (m+1) lattice points in an n X m lattice polygon.

Original entry on oeis.org

4, 16, 56, 46, 176, 520, 104, 388, 1152, 2584, 214, 822, 2502, 5700, 12368, 380, 1452, 4392, 9944, 21504, 37400, 648, 2516, 7644, 17380, 37572, 65810, 115532, 1028, 3952, 12120, 27572, 59784, 105128, 184442, 294040, 1562, 6060, 18476, 42066, 91654, 161352, 282754, 450864, 690816

Offset: 1

Hugo Pfoertner, Jun 06 2017

Chambers are counted regardless of their numbers of vertices.

The n X m lattice polygon mentioned in the definition is an n X m grid of square cells, formed using a grid of n+1 X m+1 points. - N. J. A. Sloane, Feb 07 2019

			The diagonals of the 1 X 1 lattice polygon, i.e. the square, cut it into 4 triangles. Therefore T(1,1)=4.
Triangle begins
4,
16, 56,
46, 176, 520,
104, 388, 1152, 2584,
214, 822, 2502, 5700, 12368,
...

Lars Blomberg, Table of n, a(n) for n = 1..325 (The first 25 rows)
Lars Blomberg, Colored illustration for 3 x 3
Lars Blomberg, Colored illustration for 4 X 4
Lars Blomberg, Colored illustration for 5 X 3
Lars Blomberg, Colored illustration for 5 X 5
Lars Blomberg, Scott R. Shannon, N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.
Huntington Tracy Hall, Counterexamples in Discrete Geometry. Dissertation, Department of Mathematics, University of California Berkeley, Fall 2004.
Serkan Hosten, Diane Maclagan, Bernd Sturmfels, Supernormal Vector Configurations, arXiv:math/0105036 [math.CO], 4 May 2001.
Marc E. Pfetsch, Günter M. Ziegler, Large Chambers in a Lattice Polygon (Notes), March 28, 2001, December 13, 2004.
Marc E. Pfetsch, Günter M. Ziegler, Large Chambers in a Lattice Polygon (Notes), March 28, 2001, December 13, 2004. [Cached copy, with permission]
Hugo Pfoertner, Illustrations of Chamber Complexes up to 5 X 5.

Cf. A288177, A288180, A288181.
The first column is A306302. For column 2 see A333279, A333280, A333281.
If the initial points are arranged around a circle rather than a square we get A006533 and A007678.

T(4,1) added from A306302. - N. J. A. Sloane, Feb 07 2019

T(3,3) corrected and rows for n=4..9 added by Max Alekseyev, Apr 05 2019.

A331757 Number of edges in a figure made up of a row of n adjacent congruent rectangles upon drawing diagonals of all possible rectangles.

Original entry on oeis.org

8, 28, 80, 178, 372, 654, 1124, 1782, 2724, 3914, 5580, 7626, 10352, 13590, 17540, 22210, 28040, 34670, 42760, 51962, 62612, 74494, 88508, 104042, 121912, 141534, 163664, 187942, 215636, 245490, 279260, 316022, 356456, 399898, 447612, 498698, 555352

Offset: 1

N. J. A. Sloane, Feb 04 2020

nonn

Chai Wah Wu, Table of n, a(n) for n = 1..10000
Lars Blomberg, Scott R. Shannon and N. J. A. Sloane, Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids, (2020). Also arXiv:2009.07918.

A306302 gives number of regions in the figure.
This is column 1 of A331454.
Cf. A324042, A324043.

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

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

a(n) = (2*n + 2 + 3*A324042(n) + 4*A324043(n))/2 [Corrected by Chai Wah Wu, Aug 16 2021]

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

A335678 Array read by antidiagonals: T(m,n) (m>=1, n>=1) = number of cells in figure formed by taking m equally spaced points on a line and n equally spaced points on a parallel line, and joining each of the m points to each of the n points by a line segment.

Original entry on oeis.org

0, 1, 1, 2, 4, 2, 3, 8, 8, 3, 4, 13, 16, 13, 4, 5, 19, 27, 27, 19, 5, 6, 26, 40, 46, 40, 26, 6, 7, 34, 56, 69, 69, 56, 34, 7, 8, 43, 74, 98, 104, 98, 74, 43, 8, 9, 53, 95, 130, 149, 149, 130, 95, 53, 9, 10, 64, 118, 168, 198, 214, 198, 168, 118, 64, 10, 11, 76, 144, 210, 257, 285, 285, 257, 210, 144, 76, 11

Offset: 1

Lars Blomberg, Scott R. Shannon, and N. J. A. Sloane, Jun 28 2020

The case m=n (the main diagonal) is dealt with in A306302, where there are illustrations for m = 1 to 15.

			The initial rows of the array are:
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...
  1, 4, 8, 13, 19, 26, 34, 43, 53, 64, 76, 89, ...
  2, 8, 16, 27, 40, 56, 74, 95, 118, 144, 172, 203, ...
  3, 13, 27, 46, 69, 98, 130, 168, 210, 257, 308, 365, ...
  4, 19, 40, 69, 104, 149, 198, 257, 322, 395, 474, 563, ...
  5, 26, 56, 98, 149, 214, 285, 371, 466, 573, 688, 818, ...
  6, 34, 74, 130, 198, 285, 380, 496, 624, 768, 922, 1097, ...
  7, 43, 95, 168, 257, 371, 496, 648, 816, 1005, 1207, 1437, ...
  8, 53, 118, 210, 322, 466, 624, 816, 1028, 1267, 1522, 1813, ...
  9, 64, 144, 257, 395, 573, 768, 1005, 1267, 1562, 1877, 2237, ...
  10, 76, 172, 308, 474, 688, 922, 1207, 1522, 1877, 2256, 2690, ...
  ...
The initial antidiagonals are:
  0
  1, 1
  2, 4, 2
  3, 8, 8, 3
  4, 13, 16, 13, 4
  5, 19, 27, 27, 19, 5
  6, 26, 40, 46, 40, 26, 6
  7, 34, 56, 69, 69, 56, 34, 7
  8, 43, 74, 98, 104, 98, 74, 43, 8
  9, 53, 95, 130, 149, 149, 130, 95, 53, 9
  10, 64, 118, 168, 198, 214, 198, 168, 118, 64, 10
  ...

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.
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, J. Integer Seqs., Vol. 12, 2009.
Scott R. Shannon, Colored illustration for T(2,1)
Scott R. Shannon, Colored illustration for T(2,2)
Scott R. Shannon, Colored illustration for T(3,1)
Scott R. Shannon, Colored illustration for T(3,2)
Scott R. Shannon, Colored illustration for T(3,3)
Scott R. Shannon, Colored illustration for T(4,1)
Scott R. Shannon, Colored illustration for T(4,2)
Scott R. Shannon, Colored illustration for T(4,3)
Scott R. Shannon, Colored illustration for T(4,4)
Scott R. Shannon, Colored illustration for T(5,1)
Scott R. Shannon, Colored illustration for T(5,2)
Scott R. Shannon, Colored illustration for T(5,3)
Scott R. Shannon, Colored illustration for T(5,4)
Scott R. Shannon, Colored illustration for T(5,5)
Scott R. Shannon, Colored illustration for T(6,2)
Scott R. Shannon, Colored illustration for T(6,3)
Scott R. Shannon, Colored illustration for T(6,4)
Scott R. Shannon, Colored illustration for T(6,5)
Scott R. Shannon, Colored illustration for T(6,6)
Scott R. Shannon, Colored illustration for T(7,1)
Scott R. Shannon, Colored illustration for T(7,2)
Scott R. Shannon, Colored illustration for T(7,3)
Scott R. Shannon, Colored illustration for T(7,4)
Scott R. Shannon, Colored illustration for T(7,5)
Scott R. Shannon, Colored illustration for T(7,6)
Scott R. Shannon, Colored illustration for T(7,7)
Scott R. Shannon, Colored illustration for T(8,1)
Scott R. Shannon, Colored illustration for T(8,2)
Scott R. Shannon, Colored illustration for T(8,3)
Scott R. Shannon, Colored illustration for T(8,4)
Scott R. Shannon, Colored illustration for T(8,5)
Scott R. Shannon, Colored illustration for T(8,6)
Scott R. Shannon, Colored illustration for T(8,7)
Scott R. Shannon, Colored illustration for T(8,8)
Scott R. Shannon, Colored illustration for T(14,7)
Index entries for sequences related to stained glass windows

This is one of a set of five arrays: A335678, A335679, A335680, A335681, A335682.
For the diagonal see A306302.
See also A114999.

Euler's formula implies that A335679[m,n] = A335678[m,n] + A335680[m,n] - 1 for all m,n.
Comment from Max Alekseyev, Jun 28 2020 (Start):
T(m,n) = A114999(m-1,n-1) + m*n - 1 for all m, n >= 1. This follows from the Alekseyev-Basova-Zolotykh (2015) article.
Proof: Here is the appropriate modification of the corresponding comment in A306302: Assuming that K(m,n) has vertices at (i,0) and (j,1), for i=0..m-1 and j=0..n-1, the projective map (x,y) -> ((1-y)/(x+1), y/(x+1)) maps K(m,n) to the partition of the right triangle described by Alekseyev et al. (2015), for which Theorem 13 gives the number of regions, line segments, and intersection points. (End)
Max Alekseyev's formula is an analog of Theorem 3 of Griffiths (2010), and gives an explicit formula for this array. - N. J. A. Sloane, Jun 30 2020

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

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

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

cp's OEIS Frontend

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

A288187 Triangle read by rows: T(n,m) (n >= m >= 1) = number of chambers (or regions) formed by drawing the line segments connecting any two of the (n+1) X (m+1) lattice points in an n X m lattice polygon.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions

A331757 Number of edges in a figure made up of a row of n adjacent congruent rectangles upon drawing diagonals of all possible rectangles.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

A335678 Array read by antidiagonals: T(m,n) (m>=1, n>=1) = number of cells in figure formed by taking m equally spaced points on a line and n equally spaced points on a parallel line, and joining each of the m points to each of the n points by a line segment.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

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

Views