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

%I A306302 #88 Sep 14 2022 10:42:23
%S A306302 0,4,16,46,104,214,380,648,1028,1562,2256,3208,4384,5924,7792,10052,
%T A306302 12744,16060,19880,24486,29748,35798,42648,50648,59544,69700,80992,
%U A306302 93654,107596,123374,140488,159704,180696,203684,228624,255892,285152,317400,352096,389576
%N 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).
%C A306302 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
%C A306302 The figure is made up of A324042 triangles and A324043 quadrilaterals. - _N. J. A. Sloane_, Mar 03 2020
%H A306302 Jinyuan Wang, <a href="/A306302/b306302.txt">Table of n, a(n) for n = 0..1000</a>
%H A306302 Max Alekseyev, <a href="/A306302/a306302.png">Illustration for n = 3</a>.
%H A306302 M. A. Alekseyev. <a href="https://arxiv.org/abs/math/0602511">On the number of two-dimensional threshold functions</a>, arXiv:math/0602511 [math.CO], 2006-2010; doi:<a href="http://dx.doi.org/10.1137/090750184">10.1137/090750184</a>, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.
%H A306302 M. A. Alekseyev, M. Basova, and N. Yu. Zolotykh. <a href="https://doi.org/10.1137/140978090">On the minimal teaching sets of two-dimensional threshold functions</a>, SIAM Journal on Discrete Mathematics 29:1 (2015), 157-165. doi:10.1137/140978090.
%H A306302 Lars Blomberg, Scott R. Shannon and N. J. A. Sloane, <a href="http://neilsloane.com/doc/rose_5.pdf">Graphical Enumeration and Stained Glass Windows, 1: Rectangular Grids</a>, (2020). Also arXiv:2009.07918.
%H A306302 M. Griffiths, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL13/Griffiths2/griffiths.html">Counting the regions in a regular drawing of K_{n,n}</a>, J. Int. Seq. 13 (2010) # 10.8.5, Lemma 2.
%H A306302 Robert Israel, <a href="/A306302/a306302.txt">Maple program</a>, Feb 07 2019
%H A306302 S. Legendre, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Legendre/legendre2.html">The Number of Crossings in a Regular Drawing of the Complete Bipartite Graph</a>, J. Integer Seqs., Vol. 12, 2009.
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_6.png">Colored illustration for T(1,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_7.png">Colored illustration for T(2,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_8.png">Colored illustration for T(3,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_9.png">Colored illustration for T(4,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_10.png">Colored illustration for T(5,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_11.png">Colored illustration for T(6,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_32.png">Colored illustration for T(7,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_33.png">Colored illustration for T(8,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_34.png">Colored illustration for T(9,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_35.png">Colored illustration for T(10,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_36.png">Colored illustration for T(11,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_37.png">Colored illustration for T(12,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_38.png">Colored illustration for T(13,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_39.png">Colored illustration for T(14,1)</a>
%H A306302 Scott R. Shannon, <a href="/A331452/a331452_40.png">Colored illustration for T(15,1)</a>
%H A306302 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%H A306302 <a href="/index/St#Stained">Index entries for sequences related to stained glass windows</a>
%F A306302 a(n) = n + (A114043(n+1) - 1)/2, conjectured by _N. J. A. Sloane_, Feb 07 2019; proved by _Max Alekseyev_, Apr 10 2019
%F A306302 a(n) = n + A115005(n+1) = n + A141255(n+1)/2. - _Max Alekseyev_, Apr 10 2019
%F A306302 a(n) = A324042(n) + A324043(n). - _Jinyuan Wang_, Mar 19 2020
%F A306302 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
%F A306302 a(n) = 2n(n+1) + Sum_{i=2..n} (n+1-i)*(2n+2-i)*phi(i). - _Chai Wah Wu_, Aug 16 2021
%p A306302 # Maple from _N. J. A. Sloane_, Mar 04 2020, starting at n=1:  First define z(n) = A115004
%p A306302 z := proc(n)
%p A306302     local a, b, r ;
%p A306302     r := 0 ;
%p A306302     for a from 1 to n do
%p A306302     for b from 1 to n do
%p A306302         if igcd(a, b) = 1 then
%p A306302             r := r+(n+1-a)*(n+1-b);
%p A306302         end if;
%p A306302     end do:
%p A306302     end do:
%p A306302     r ;
%p A306302 end proc:
%p A306302 a := n-> z(n)+n^2+2*n;
%p A306302 [seq(a(n), n=1..50)];
%t A306302 z[n_] := Sum[(n - i + 1)(n - j + 1) Boole[GCD[i, j] == 1], {i, n}, {j, n}];
%t A306302 a[0] = 0;
%t A306302 a[n_] := z[n] + n^2 + 2n;
%t A306302 a /@ Range[0, 40] (* _Jean-François Alcover_, Mar 24 2020 *)
%o A306302 (Python)
%o A306302 from sympy import totient
%o A306302 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
%Y A306302 See A331755 for the number of vertices, A331757 for the number of edges.
%Y A306302 Cf. A007678, A108914, A114043, A324042, A324043, A333286, A333287, A333288, A334694.
%Y A306302 A column of A288187. See A288177 for additional references.
%Y A306302 Also a column of A331452 and A356790.
%Y A306302 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
%K A306302 nonn
%O A306302 0,2
%A A306302 _Paarth Jain_, Feb 05 2019
%E A306302 a(6)-a(20) from _Robert Israel_, Feb 07 2019
%E A306302 Edited and more terms added by _Max Alekseyev_, Apr 10 2019
%E A306302 a(0) added by _N. J. A. Sloane_, Feb 04 2020