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

4, 14, 32, 70, 124, 226, 360, 566, 820, 1218, 1696, 2310, 3020, 4018, 5160, 6590, 8196, 10218, 12464, 15110, 18012, 21650, 25624, 30142, 35028, 40954, 47344, 54558, 62284, 71034, 80360, 90806, 101892, 114770, 128416, 143286, 158972, 176914, 195816, 216350, 237908, 261546, 286304, 313102, 341100

Offset

1,1

Comments

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.

Links

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

Formula

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

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

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

Example

For k adjacent congruent rectangles, the number of triangular regions in the j-th rectangle is:
k\j|  1   2   3   4   5   6   7  ...
---+--------------------------------
1  |  4,  0,  0,  0,  0,  0,  0, ...
2  |  7,  7,  0,  0,  0,  0,  0, ...
3  |  9, 14,  9,  0,  0,  0,  0, ...
4  | 11, 24, 24, 11,  0,  0,  0, ...
5  | 13, 30, 38, 30, 13,  0,  0, ...
6  | 15, 38, 60, 60, 38, 15,  0, ...
7  | 17, 44, 76, 86, 76, 44, 17, ...
...
a(4) = 11 + 24 + 24 + 11 = 70.

Maple

V := proc(m, n, q) local a, i, j; a:=0;
for i from 1 to m do for j from 1 to n do
if gcd(i, j)=q then a:=a+(m+1-i)*(n+1-j); fi; od: od: a; end;
a := n -> 2*( n*(n+1) + V(n, n, 2) );
[seq(a(n), n=1..30)]; # N. J. A. Sloane, Mar 04 2020
See also Robert Israel link.

Mathematica

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

Prog

(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
(Python)
from sympy import totient
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

Crossrefs

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

Sequence in context: A023627 A023649 A323723 * A099590 A078432 A124786

Adjacent sequences: A324039 A324040 A324041 * A324043 A324044 A324045

Keyword

nonn

Author

Jinyuan Wang, May 01 2019

Extensions

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

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

Status

approved