# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a114043
Showing 1-1 of 1

%I A114043 #41 Aug 16 2021 13:47:56
%S A114043 1,7,29,87,201,419,749,1283,2041,3107,4493,6395,8745,11823,15557,
%T A114043 20075,25457,32087,39725,48935,59457,71555,85253,101251,119041,139351,
%U A114043 161933,187255,215137,246691,280917,319347,361329,407303
%N A114043 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 A114043 Also, half of the number of two-dimensional threshold functions (A114146).
%C A114043 The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696).
%C A114043 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 A114043 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 A114043 What can be said about the 3-D generalization? - _Max Alekseyev_, Feb 27 2006
%H A114043 T. D. Noe, <a href="/A114043/b114043.txt">Table of n, a(n) for n = 1..1000</a>
%H A114043 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 A114043 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 A114043 N. J. A. Sloane, <a href="/A115004/a115004.txt">Families of Essentially Identical Sequences</a>, Mar 24 2021 (Includes this sequence)
%F A114043 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 A114043 a(n) ~ (3/Pi^2) * n^4. - _Max Alekseyev_, Feb 22 2006
%F A114043 a(n) = A141255(n) + 1. - _T. D. Noe_, Jun 17 2008
%F A114043 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 A114043 Examples: the two sets are indicated by X's and o's.
%e A114043 a(2) = 7:
%e A114043 XX oX Xo XX XX oo oX
%e A114043 XX XX XX Xo oX XX oX
%e A114043 --------------------
%e A114043 a(3) = 29:
%e A114043 XXX oXX ooX ooo ooX ooo
%e A114043 XXX XXX XXX XXX oXX oXX
%e A114043 XXX XXX XXX XXX XXX XXX
%e A114043 -1- -4- -8- -4- -4- -8- Total = 29
%e A114043 --------------------
%e A114043 a(4)= 87:
%e A114043 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
%e A114043 XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
%e A114043 XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo
%e A114043 XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo
%e A114043 --1- --4- --8- --8- --4- --4- --8- --8- --8- --8-
%e A114043 XXXX XXXX XXXX XXXX XXXX
%e A114043 XXXo XXXX XXXX XXXo XXXo
%e A114043 XXoo Xooo oooo Xooo XXoo
%e A114043 Xooo oooo oooo oooo oooo
%e A114043 --4- --8- --2- --4- --8- Total = 87.
%e A114043 --------------------
%t A114043 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 A114043 (Python)
%o A114043 from sympy import totient
%o A114043 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 A114043 Cf. A114499, A115004, A115005, A116696 (unlabeled case), A114531, A114146.
%Y A114043 Cf. A099957.
%Y A114043 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 A114043 nonn,nice
%O A114043 1,2
%A A114043 Ugo Merlone (merlone(AT)econ.unito.it) and _N. J. A. Sloane_, Feb 22 2006
%E A114043 More terms from _Max Alekseyev_, Feb 22 2006

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE