BBC Russian

A114146

Number of threshold functions on n X n grid.

1, 2, 14, 58, 174, 402, 838, 1498, 2566, 4082, 6214, 8986, 12790, 17490, 23646, 31114, 40150, 50914, 64174, 79450, 97870, 118914, 143110, 170506, 202502, 238082, 278702, 323866, 374510, 430274, 493382, 561834, 638694, 722658, 814606, 914362, 1023430, 1140466 (list; graph; refs; listen; history; text; internal format)

	OFFSET	`0,2`
	COMMENTS	`Also, number of intersections of a halfspace with an n X n grid. While A114043 counts cuts, this sequence counts sides of cuts. The only difference between this and twice A114043 is that this makes sense for the empty grid. This is the "labeled" version - rotations and reflections are not taken into account. - David Applegate, Feb 24 2006` `In the terminology of Koplowitz et al., this is the number of linear dichotomies on a square grid. - N. J. A. Sloane, Mar 14 2020`
	LINKS	`Chai Wah Wu, Table of n, a(n) for n = 0..10000` `M. A. Alekseyev. On the number of two-dimensional threshold functions, arXiv:math/0602511 [math.CO], 2006-2010; doi:10.1137/090750184, SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631.` `M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. On the minimal teaching sets of two-dimensional threshold functions. SIAM J. Disc. Math. 29(1), 2015, pp. 157-165.` `Jack Koplowitz, Michael Lindenbaum and A. Bruckstein, The number of digital straight lines on an N*N grid, IEEE Transactions on Information Theory 36.1 (1990): 192-197. See D(n).` `N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)`
	FORMULA	`For n>0, a(n) = 2A114043(n).` `For n>0, a(n) = 8n^2 - 12n + 6 + 4Sum_{i=2..n-1} (n-i)(2n-i)phi(i). - Chai Wah Wu, Aug 15 2021`
	MATHEMATICA	`a[0] = 1; a[n_] := 4 Sum[(n-i)(n-j) Boole[CoprimeQ[i, j]], {i, 1, n-1}, {j, 1, n-1}] + 4 n^2 - 4 n + 2;` `Array[a, 38, 0] (* Jean-François Alcover, Sep 04 2018, after Max Alekseyev in A114043 *)`
	PROG	`(Python)` `from sympy import totient` `def A114146(n): return 1 if n == 0 else 8n2-12n+6 + 4sum(totient(i)(n-i)(2n-i) for i in range(2, n)) # Chai Wah Wu, Aug 15 2021`
	CROSSREFS	`Cf. A114043, A114531.` `The following eight sequences are all essentially the same. The simplest is A115004(n), which we denote by z(n). Then A088658(n) = 4z(n-1); A114043(n) = 2z(n-1)+2n^2-2n+1; A114146(n) = 2A114043(n); A115005(n) = z(n-1)+n(n-1); A141255(n) = 2z(n-1)+2n(n-1); A290131(n) = z(n-1)+(n-1)^2; A306302(n) = z(n)+n^2+2n. - N. J. A. Sloane, Feb 04 2020` `Sequence in context: A178605 A212895 A115027 * A096367 A232601 A285153` `Adjacent sequences: A114143 A114144 A114145 * A114147 A114148 A114149`
	KEYWORD	`nonn`
	AUTHOR	`N. J. A. Sloane, Feb 22 2006`
	EXTENSIONS	`Definition corrected by Max Alekseyev, Oct 23 2008` `a(0)=1 prepended by Max Alekseyev, Jan 23 2015`
	STATUS	`approved`