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.

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,2

Comments

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.

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

Example

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.

Maple

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

Mathematica

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

Prog

(PARI) { 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
(Python)
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

Crossrefs

Cf. A007678, A108914, A114043, A115005, A177719, A306302, A324042, A333286, A333287, A333288.

Sequence in context: A060626 A096311 A034842 * A230894 A291152 A145910

Adjacent sequences: A324040 A324041 A324042 * A324044 A324045 A324046

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