login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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): 192-197. (See D(n).)

LINKS

Table of n, a(n) for n=0..37.

M. A. Alekseyev. On the number of two-dimensional threshold functions. SIAM J. Disc. Math. 24(4), 2010, pp. 1617-1631. doi:10.1137/090750184

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.

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[(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 *)

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(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

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified June 24 18:46 EDT 2021. Contains 345419 sequences. (Running on oeis4.)