|
%I #49 Aug 16 2021 14:47:17
%S 0,2,14,34,90,154,288,462,742,1038,1512,2074,2904,3774,4892,6154,7864,
%T 9662,12022,14638,17786,20998,25024,29402,34672,40038,46310,53038,
%U 61090,69454,79344,89890,101792,113854,127476,141866,158428,175182,193760,213274,235444,258182,283858,310750,339986
%N 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.
%C 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.
%H Chai Wah Wu, <a href="/A324043/b324043.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="/A324043/a324043.txt">Maple program</a>.
%H Jinyuan Wang, <a href="/A324043/a324043.png">Illustration for n = 1, 2, 3, 4, 5</a>.
%F 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
%F a(n) = A306302(n) - A324042(n).
%F 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
%e For k adjacent congruent rectangles, the number of quadrilateral regions in the j-th rectangle is:
%e k\j| 1 2 3 4 5 6 7 ...
%e ---+--------------------------------
%e 1 | 0, 0, 0, 0, 0, 0, 0, ...
%e 2 | 1, 1, 0, 0, 0, 0, 0, ...
%e 3 | 3, 8, 3, 0, 0, 0, 0, ...
%e 4 | 5, 12, 12, 5, 0, 0, 0, ...
%e 5 | 7, 22, 32, 22, 7, 0, 0, ...
%e 6 | 9, 28, 40, 40, 28, 9, 0, ...
%e 7 | 11, 38, 58, 74, 58, 38, 11, ...
%e ...
%e a(4) = 5 + 12 + 12 + 5 = 34.
%p See Robert Israel link.
%p There are also Maple programs for both A306302 and A324042. Then a := n -> A306302(n) - A324042(n); # _N. J. A. Sloane_, Mar 04 2020
%t 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 *)
%o (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
%o (Python)
%o from sympy import totient
%o 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
%Y Cf. A007678, A108914, A114043, A115005, A177719, A306302, A324042, A333286, A333287, A333288.
%K nonn
%O 1,2
%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
|
