|
Search: id:A114043
|
|
|
| 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. |
|
+0
11
|
|
| 1, 7, 29, 87, 201, 419, 749, 1283, 2041, 3107, 4493, 6395, 8745, 11823, 15557, 20075, 25457, 32087, 39725, 48935, 59457, 71555, 85253, 101251, 119041, 139351, 161933, 187255, 215137, 246691, 280917, 319347, 361329, 407303
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
Also, number of two-dimensional threshold functions.
The line may not pass through any point. This is the "labeled" version - rotations and reflections are not taken into account (cf. A116696).
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 (david(AT)research.att.com), Feb 23 2006
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.
What can be said about the 3-D generalization? - Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 27, 2006
|
|
LINKS
|
T. D. Noe, Table of n, a(n) for n=1..1000
Max Alekseyev, On the number of two-dimensional threshold functions
|
|
FORMULA
|
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 (maxal(AT)cs.ucsd.edu), Feb 22 2006
a(n) ~ (3/pi^2) * n^4. - Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 22 2006
a(n) = A141255(n) + 1. - T. D. Noe, Jun 17 2008
|
|
EXAMPLE
|
Examples: the two sets are indicated by X's and o's.
a(2) = 7:
XX oX Xo XX XX oo oX
XX XX XX Xo oX XX oX
--------------------
a(3) = 29:
XXX oXX ooX ooo ooX ooo
XXX XXX XXX XXX oXX oXX
XXX XXX XXX XXX XXX XXX
-1- -4- -8- -4- -4- -8- Total = 29
--------------------
a(4)= 87:
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX XXXX
XXXX XXXX XXXX XXXX XXXX XXXo XXXo XXXo XXoo XXoo
XXXX XXXo XXoo Xooo oooo XXoo Xooo oooo Xooo oooo
--1- --4- --8- --8- --4- --4- --8- --8- --8- --8-
XXXX XXXX XXXX XXXX XXXX
XXXo XXXX XXXX XXXo XXXo
XXoo Xooo oooo Xooo XXoo
Xooo oooo oooo oooo oooo
--4- --8- --2- --4- --8- Total = 87.
--------------------
|
|
CROSSREFS
|
Cf. A114499, A115004, A115005; A116696 (unlabeled case), A114531, A115027.
Cf. A099957.
Sequence in context: A022272 A141854 A079796 this_sequence A001779 A053295 A055798
Adjacent sequences: A114040 A114041 A114042 this_sequence A114044 A114045 A114046
|
|
KEYWORD
|
nonn,nice
|
|
AUTHOR
|
Ugo Merlone (merlone(AT)econ.unito.it) and njas, Feb 22 2006
|
|
EXTENSIONS
|
More terms from Max Alekseyev (maxal(AT)cs.ucsd.edu), Feb 22, 2006
|
|
|
Search completed in 0.002 seconds
|
