A108914 -id:A108914 - cp's OEIS frontend

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

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

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

A357058 Number of regions in a square when n internal squares are drawn between the 4n points that divide each side into n+1 equal parts.

Original entry on oeis.org

1, 5, 17, 37, 65, 93, 145, 181, 257, 309, 401, 457, 577, 653, 785, 869, 1025, 1109, 1297, 1413, 1601, 1725, 1937, 2041, 2305, 2453, 2705, 2861, 3137, 3289, 3601, 3765, 4089, 4293, 4625, 4801, 5185, 5405, 5769, 5993, 6401, 6605, 7057, 7309, 7737, 8013, 8465, 8673, 9217, 9477, 9993, 10309

Offset: 0

Scott R. Shannon, Sep 10 2022

nonn

The even values of n that yield squares with non-simple intersections are 32, 38, 44, 50, 54, 62, 76, 90, 98, ... .

Scott R. Shannon, Image for n = 1.
Scott R. Shannon, Image for n = 2.
Scott R. Shannon, Image for n = 3.
Scott R. Shannon, Image for n = 5. This is the first term that forms squares with non-simple intersections.
Scott R. Shannon, Image for n = 10.
Scott R. Shannon, Image for n = 32. This is the first term with n mod 2 = 0 that forms squares with non-simple intersections.
Scott R. Shannon, Image for n = 200.

Cf. A357060 (vertices), A357061 (edges), A108914, A355838, A355798, A356984 (triangle).

a(n) = A357061(n) - A357060 (n) + 1 by Euler's formula.

Conjecture: a(n) = 4*n^2 + 1 for squares that only contain simple intersections when cut by n internal squares. This is never the case for odd n >= 5.

A355949 Number of vertices formed in a square by straight line segments when connecting the four corner vertices to the points dividing the sides into n equal parts.

Original entry on oeis.org

5, 25, 81, 157, 301, 381, 665, 821, 1109, 1353, 1825, 1861, 2621, 2881, 3285, 3813, 4645, 4773, 5873, 5953, 6821, 7665, 8761, 8613, 10165, 10921, 11777, 12337, 14173, 13717, 16265, 16581, 17861, 19161, 20093, 20461, 23405, 24145, 25305, 25701, 28885, 28433, 31841, 32077, 33269, 35841, 38185

Offset: 1

Scott R. Shannon, Jul 21 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 = 11.

Cf. A108914 (regions), A355948 (edges), A355992 (k-gons), A355839, A331452, A335678.

a(n) = A355948(n) - A108914(n) + 1 by Euler's formula.

A278823 4-Portolan numbers: number of regions formed by n-secting the angles of a square.

Original entry on oeis.org

1, 4, 29, 32, 93, 84, 189, 188, 321, 316, 489, 460, 693, 676, 933, 916, 1205, 1180, 1505, 1496, 1849, 1836, 2229, 2188, 2645, 2616, 3097, 3060, 3577, 3536, 4089, 4064, 4645, 4604, 5237, 5176, 5857, 5808, 6513, 6472, 7201, 7160, 7933, 7900, 8693, 8648, 9497

Offset: 1

Ethan Beihl, Nov 28 2016

nonn

m-Portolan numbers for m>3 (especially m even) are more difficult than m=3 (A277402) because Ceva's theorem doesn't immediately give us a condition for redundant intersections. The values for n <= 23 were found by brute force in Mathematica, as follows:
1. Solve for the coordinates of all intersections between lines within the square, recording multiplicity.
2. Use an elementary Euler's-formula method as in Poonen and Rubinstein 1998 to turn the intersection-count into a region-count.

			For n=3, the 4*(3-1) = 8 lines intersect to make 12 triangles, 8 kites, 8 irregular quadrilaterals, and an octagon in the middle. The total number of regions a(3) is therefore 12+8+8+1 = 29.

Lars Blomberg, Table of n, a(n) for n = 1..500
Ethan Beihl, Pictures for some small n
Lars Blomberg, Coloured illustration for n=4
Lars Blomberg, Coloured illustration for n=5
Lars Blomberg, Coloured illustration for n=64
Lars Blomberg, Coloured illustration for n=65
B. Poonen and M. Rubinstein (1998) The Number of Intersection Points Made by the Diagonals of a Regular Polygon, SIAM J. Discrete Mathematics 11(1), pp. 135-156, doi:10.1137/S0895480195281246, arXiv:math.MG/9508209 (typos corrected)

3-Portolan numbers (equilateral triangle): A277402.
n-sected sides (not angles): A108914.
Cf. A277402, A335526 (vertices), A335527 (edges), A335528 (ngons).

For n = 2k - 1, a(n) is close to 18k^2 - 26k + 9. For n = 2k, a(n) is close to 18k^2 - 26k + 12. The residuals are related to the structure of redundant intersections in the figure.

a(24) and beyond from Lars Blomberg, Jun 12 2020

A355948 Number of edges formed in a square by straight line segments when connecting the four corner vertices to the points dividing the sides into n equal parts.

Original entry on oeis.org

8, 56, 176, 344, 632, 840, 1376, 1736, 2312, 2840, 3728, 3968, 5336, 5960, 6816, 7880, 9416, 9912, 11888, 12344, 14008, 15656, 17696, 17872, 20648, 22232, 23984, 25304, 28568, 28376, 32768, 33800, 36296, 38840, 40848, 42008, 47096, 48872, 51296, 52568, 58088, 58136, 64016, 65144, 67712, 72392

Offset: 1

Scott R. Shannon, Jul 21 2022

nonn

See A108914 for images of the squares.

Cf. A108914 (regions), A355949 (vertices), A355992 (k-gons), A355840, A331452, A335678.

a(n) = A108914(n) + A355949(n) - 1 by Euler's formula.

A355992 Irregular table read by rows: T(n,k) is the number of k-sided polygons formed, for k>=3, in a square when straight line segments connect the four corner vertices to the points dividing the sides into n equal parts.

Original entry on oeis.org

4, 24, 8, 56, 28, 12, 96, 80, 8, 4, 144, 140, 36, 12, 216, 216, 24, 4, 272, 332, 76, 24, 8, 360, 448, 80, 28, 456, 572, 132, 36, 8, 568, 728, 128, 64, 656, 916, 260, 28, 40, 4, 792, 1104, 176, 36, 928, 1308, 316, 128, 32, 4, 1064, 1568, 304, 128, 16, 1240, 1772, 396, 88, 32, 4, 1416, 2032, 432, 156, 32

Offset: 1

Scott R. Shannon, Jul 22 2022

Up to n = 100 the maximum sided k-gon created is the 8-gon. It is plausible this is the maximum sided k-gon for all n, although this is unknown.

See A108914 for more images of the square.

			The table begins:
4;
24,   8;
56,   28,   12;
96,   80,   8,   4;
144,  140,  36,  12;
216,  216,  24,  4;
272,  332,  76,  24,  8;
360,  448,  80,  28;
456,  572,  132, 36,  8;
568,  728,  128, 64;
656,  916,  260, 28,  40, 4;
792,  1104, 176, 36;
928,  1308, 316, 128, 32, 4;
1064, 1568, 304, 128, 16;
1240, 1772, 396, 88,  32, 4;
1416, 2032, 432, 156, 32;
.
.

Scott R. Shannon, Image for n = 13.

Cf. A108914 (regions), A355948 (edges), A355949 (vertices), A355841, A331452, A335678.

A356044 Table read by antidiagonals: T(n,k) (n >= 3, k >= 1) is the number of regions formed in a regular n-gon by straight line segments when connecting the n corner vertices to the points dividing the sides into k equal parts.

Original entry on oeis.org

1, 6, 4, 19, 32, 11, 30, 96, 90, 24, 61, 188, 316, 246, 50, 78, 332, 580, 672, 462, 80, 127, 460, 1081, 1476, 1590, 856, 154, 150, 712, 1510, 2442, 2982, 2688, 1476, 220, 217, 916, 2306, 3528, 5370, 5504, 4861, 2420, 375, 246, 1204, 2930, 5310, 7742, 9440, 9288, 7360, 3630, 444

Offset: 3

Scott R. Shannon, Jul 31 2022

			The table begins:
1,    6,     19,     30,     61,     78,     127,    150,     217,     246,...
4,    32,    96,     188,    332,    460,    712,    916,     1204,    1488,...
11,   90,    316,    580,    1081,   1510,   2306,   2930,    3961,    4780,...
24,   246,   672,    1476,   2442,   3528,   5310,   7176,    9072,    11352,...
50,   462,   1590,   2982,   5370,   7742,   11390,  14742,   19650,   23982,...
80,   856,   2688,   5504,   9440,   13968,  20216,  27008,   34888,   43792,...
154,  1476,  4861,   9288,   16408,  23886,  34741,  45324,   59860,   73548,...
220,  2420,  7360,   14980,  25480,  37690,  54180,  72280,   93400,   116970,...
375,  3630,  11661,  22374,  39051,  57222,  82545,  108174,  142143,  175230,...
444,  5400,  15864,  32532,  55500,  82032,  118056, 157236,  203148,  254184,...
781,  7566,  23804,  45890,  79431,  116818, 167662, 220350,  288497,  356486,...
952,  10668, 31682,  63700,  107184, 160874, 226996, 303324,  390950,  489860,...
1456, 14070, 43546,  84270,  144976, 213720, 305656, 402510,  525586,  650550,...
1696, 18832, 55792,  111840, 187776, 282000, 397072, 530432,  683616,  855920,...
2500, 24072, 73645,  142732, 244410, 361012, 514795, 678912,  884800,  1096432,...
2466, 30078, 91080,  181746, 306522, 458334, 647766, 864234,  1114668, 1394586,...
4029, 38646, 117079, 227278, 387753, 573534, 816051, 1077414, 1401973, 1738918,...
.
.
See the attached text file for more examples and the cross references for further images.

Scott R. Shannon, Image of T(5,9) = 3961.
Scott R. Shannon, Image of T(6,8) = 7176.
Scott R. Shannon, Image of T(7,5) = 5370.
Scott R. Shannon, Image of T(8,4) = 5504.
Scott R. Shannon, Image of T(12,4) = 32532.
Scott R. Shannon, Image of T(14,6) = 160874.
Scott R. Shannon, Table for n = 3..25.

Cf. A007678 (first column), A092098 (first row), A108914 (second row).

T(n,1) = A007678(n).
T(3,k) = A092098(k).
T(4,k) = A108914(k).

cp's OEIS Frontend

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

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions

A357058 Number of regions in a square when n internal squares are drawn between the 4n points that divide each side into n+1 equal parts.

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

A355949 Number of vertices formed in a square by straight line segments when connecting the four corner vertices to the points dividing the sides into n equal parts.

Views

Author

Keywords

Links

Crossrefs

Formula

A278823 4-Portolan numbers: number of regions formed by n-secting the angles of a square.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions

A355948 Number of edges formed in a square by straight line segments when connecting the four corner vertices to the points dividing the sides into n equal parts.

Views

Author

Keywords

Comments

Crossrefs

Formula

A355992 Irregular table read by rows: T(n,k) is the number of k-sided polygons formed, for k>=3, in a square when straight line segments connect the four corner vertices to the points dividing the sides into n equal parts.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A356044 Table read by antidiagonals: T(n,k) (n >= 3, k >= 1) is the number of regions formed in a regular n-gon by straight line segments when connecting the n corner vertices to the points dividing the sides into k equal parts.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula