|
%I #41 Aug 16 2021 13:47:56
%S 1,7,29,87,201,419,749,1283,2041,3107,4493,6395,8745,11823,15557,
%T 20075,25457,32087,39725,48935,59457,71555,85253,101251,119041,139351,
%U 161933,187255,215137,246691,280917,319347,361329,407303
%N Take an n X n square grid of points in the plane; a(n) = number of ways to divide the points into two sets using a straight line.
%C Also, half of the number of two-dimensional threshold functions (A114146).
%C The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696).
%C The number of ways to divide a (2n) X (2n) grid into two sets of equal size is given by 2*A099957(n). - _David Applegate_, Feb 23 2006
%C All terms are odd: the line that misses the grid contributes 1 to the total and all other lines contribute 2, 4 or 8, so the total must be odd.
%C What can be said about the 3-D generalization? - _Max Alekseyev_, Feb 27 2006
%H T. D. Noe, <a href="/A114043/b114043.txt">Table of n, a(n) for n = 1..1000</a>
%H Max 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 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. See Eq. (11).
%H N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%F Let V(m,n) = Sum_{i=1..m, j=1..n, gcd(i,j)=1} (m+1-i)*(n+1-j); then a(n+1) = 2*(n^2 + n + V(n,n)) + 1. - _Max Alekseyev_, Feb 22 2006
%F a(n) ~ (3/Pi^2) * n^4. - _Max Alekseyev_, Feb 22 2006
%F a(n) = A141255(n) + 1. - _T. D. Noe_, Jun 17 2008
%F a(n) = 4*n^2 - 6*n + 3 + 2*Sum_{i=2..n-1} (n-i)*(2n-i)*phi(i). - _Chai Wah Wu_, Aug 15 2021
%e Examples: the two sets are indicated by X's and o's.
%e a(2) = 7:
%e XX oX Xo XX XX oo oX
%e XX XX XX Xo oX XX oX
%e --------------------
%e a(3) = 29:
%e XXX oXX ooX ooo ooX ooo
%e XXX XXX XXX XXX oXX oXX
%e XXX XXX XXX XXX XXX XXX
%e -1- -4- -8- -4- -4- -8- Total = 29
%e --------------------
%e a(4)= 87:
%e XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
%e XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
%e XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo
%e XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo
%e --1- --4- --8- --8- --4- --4- --8- --8- --8- --8-
%e XXXX XXXX XXXX XXXX XXXX
%e XXXo XXXX XXXX XXXo XXXo
%e XXoo Xooo oooo Xooo XXoo
%e Xooo oooo oooo oooo oooo
%e --4- --8- --2- --4- --8- Total = 87.
%e --------------------
%t a[n_] := 2*Sum[(n - i)*(n - j)*Boole[CoprimeQ[i, j]], {i, 1, n - 1}, {j, 1, n - 1}] + 2*n^2 - 2*n + 1; Array[a, 40] (* _Jean-François Alcover_, Apr 25 2016, after _Max Alekseyev_ *)
%o (Python)
%o from sympy import totient
%o def A114043(n): return 4*n**2-6*n+3 + 2*sum(totient(i)*(n-i)*(2*n-i) for i in range(2,n)) # _Chai Wah Wu_, Aug 15 2021
%Y Cf. A114499, A115004, A115005, A116696 (unlabeled case), A114531, A114146.
%Y Cf. A099957.
%Y 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 nonn,nice
%O 1,2
%A Ugo Merlone (merlone(AT)econ.unito.it) and _N. J. A. Sloane_, Feb 22 2006
%E More terms from _Max Alekseyev_, Feb 22 2006
| 