A324042 - OEIS

%I #57 Aug 16 2021 13:47:05

%S 4,14,32,70,124,226,360,566,820,1218,1696,2310,3020,4018,5160,6590,

%T 8196,10218,12464,15110,18012,21650,25624,30142,35028,40954,47344,

%U 54558,62284,71034,80360,90806,101892,114770,128416,143286,158972,176914,195816,216350,237908,261546,286304,313102,341100

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

%C A row of n adjacent congruent rectangles can only be divided into triangles or quadrilaterals when drawing diagonals. A proof is given in Alekseyev et al. (2015) using the mapping to a dissection of a a right isosceles triangle described in A306302.

%H Chai Wah Wu, <a href="/A324042/b324042.txt">Table of n, a(n) for n = 1..10000</a>

%H 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.

%H 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>, (2021). Also arXiv:2009.07918.

%H Robert Israel, <a href="/A324042/a324042.txt">Maple program</a>

%H Jinyuan Wang, <a href="/A324042/a324042.png">Illustration for n = 1, 2, 3, 4, 5</a>

%F a(n) = A177719(n+1) + 2*(n+1) = 2 * ( (n+1)*n + Sum_{i,j=1..n; gcd(i,j)=2} (n+1-i)*(n+1-j) ). - _Max Alekseyev_, Jul 08 2019

%F a(n) = A306302(n) - A324043(n).

%F a(n) = 2*(2*n^2-n+1+2*Sum_{i=2..floor(n/2)} (n+1-2*i)*(n+1-i)*phi(i)). - _Chai Wah Wu_, Aug 16 2021

%e For k adjacent congruent rectangles, the number of triangular regions in the j-th rectangle is:

%e k\j|  1   2   3   4   5   6   7  ...

%e ---+--------------------------------

%e 1  |  4,  0,  0,  0,  0,  0,  0, ...

%e 2  |  7,  7,  0,  0,  0,  0,  0, ...

%e 3  |  9, 14,  9,  0,  0,  0,  0, ...

%e 4  | 11, 24, 24, 11,  0,  0,  0, ...

%e 5  | 13, 30, 38, 30, 13,  0,  0, ...

%e 6  | 15, 38, 60, 60, 38, 15,  0, ...

%e 7  | 17, 44, 76, 86, 76, 44, 17, ...

%e ...

%e a(4) = 11 + 24 + 24 + 11 = 70.

%p V := proc(m,n,q) local a,i,j; a:=0;

%p for i from 1 to m do for j from 1 to n do

%p if gcd(i,j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;

%p a := n -> 2*( n*(n+1) + V(n,n,2) );

%p [seq(a(n), n=1..30)]; # _N. J. A. Sloane_, Mar 04 2020

%p See also Robert Israel link.

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

%o (PARI) { A324042(n) = 2*((n+1)*n + sum(i=1, n, sum(j=1, n, (gcd(i, j)==2)*(n+1-i)*(n+1-j))) ); } \\ _Max Alekseyev_, Jul 08 2019

%o (Python)

%o from sympy import totient

%o def A324042(n): return 2*(2*n**2-n+1 + 2*sum(totient(i)*(n+1-2*i)*(n+1-i) for i in range(2,n//2+1))) # _Chai Wah Wu_, Aug 16 2021

%Y Cf. A177719, A306302, A324043, A333286, A333287, A333288.

%K nonn

%O 1,1

%A _Jinyuan Wang_, May 01 2019

%E a(8)-a(23) from _Robert Israel_, Jul 07 2019

%E Terms a(24) onward from _Max Alekseyev_, Jul 08 2019