

A114146


Number of threshold functions on n X n grid.


12



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


REFERENCES

Koplowitz, Jack, Michael Lindenbaum, and A. Bruckstein. "The number of digital straight lines on an N* N grid." IEEE Transactions on Information Theory 36.1 (1990): 192197. (See D(n).)


LINKS

Table of n, a(n) for n=0..37.
M. A. Alekseyev. On the number of twodimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 16171631. doi:10.1137/090750184
M. A. Alekseyev, M. Basova, N. Yu. Zolotykh. On the minimal teaching sets of twodimensional threshold functions. SIAM J. Disc. Math. 29(1), 2015, pp. 157165.
N. J. A. Sloane, Families of Essentially Identical Sequences, Mar 24 2021 (Includes this sequence)


FORMULA

For n>0, a(n) = 2*A114043(n).


MATHEMATICA

a[0] = 1; a[n_] := 4 Sum[(ni)(nj) Boole[CoprimeQ[i, j]], {i, 1, n1}, {j, 1, n1}] + 4 n^2  4 n + 2;
Array[a, 38, 0] (* JeanFrançois Alcover, Sep 04 2018, after Max Alekseyev in A114043 *)


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) = 4*z(n1); A114043(n) = 2*z(n1)+2*n^22*n+1; A114146(n) = 2*A114043(n); A115005(n) = z(n1)+n*(n1); A141255(n) = 2*z(n1)+2*n*(n1); A290131(n) = z(n1)+(n1)^2; A306302(n) = z(n)+n^2+2*n.  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



