A178256 -id:A178256 - cp's OEIS frontend

A157882 Number of collinear point-triples in the n X n X n cube.

0, 0, 49, 376, 1858, 5696, 16427, 36992, 78204, 150672, 277005, 463624, 776494, 1212208, 1845911, 2749568, 4023608, 5654976, 7915497, 10730616, 14487706, 19290352, 25343011, 32580752, 41959412, 53240624, 66913605, 83330712

Offset: 1

R. J. Mathar, May 21 2010

nonn

A 3D variant of A000938.

			For n=3, for example, the 49 collinear triples have coordinates (sorting according to the base-n representation of numbers from 0 to n^3-1):
[0, 0, 0], [1, 0, 0], [2, 0, 0]
[0, 0, 0], [0, 1, 0], [0, 2, 0]
[0, 0, 0], [1, 1, 0], [2, 2, 0]
[0, 0, 0], [0, 0, 1], [0, 0, 2]
[0, 0, 0], [1, 0, 1], [2, 0, 2]
[0, 0, 0], [0, 1, 1], [0, 2, 2]
[0, 0, 0], [1, 1, 1], [2, 2, 2]
[1, 0, 0], [1, 1, 0], [1, 2, 0]
[1, 0, 0], [1, 0, 1], [1, 0, 2]
[1, 0, 0], [1, 1, 1], [1, 2, 2]
[2, 0, 0], [1, 1, 0], [0, 2, 0]
[2, 0, 0], [2, 1, 0], [2, 2, 0]
[2, 0, 0], [1, 0, 1], [0, 0, 2]
[2, 0, 0], [2, 0, 1], [2, 0, 2]
[2, 0, 0], [1, 1, 1], [0, 2, 2]
[2, 0, 0], [2, 1, 1], [2, 2, 2]
[0, 1, 0], [1, 1, 0], [2, 1, 0]
[0, 1, 0], [0, 1, 1], [0, 1, 2]
[0, 1, 0], [1, 1, 1], [2, 1, 2]
[1, 1, 0], [1, 1, 1], [1, 1, 2]
[2, 1, 0], [1, 1, 1], [0, 1, 2]
[2, 1, 0], [2, 1, 1], [2, 1, 2]
[0, 2, 0], [1, 2, 0], [2, 2, 0]
[0, 2, 0], [0, 1, 1], [0, 0, 2]
[0, 2, 0], [1, 1, 1], [2, 0, 2]
[0, 2, 0], [0, 2, 1], [0, 2, 2]
[0, 2, 0], [1, 2, 1], [2, 2, 2]
[1, 2, 0], [1, 1, 1], [1, 0, 2]
[1, 2, 0], [1, 2, 1], [1, 2, 2]
[2, 2, 0], [1, 1, 1], [0, 0, 2]
[2, 2, 0], [2, 1, 1], [2, 0, 2]
[2, 2, 0], [1, 2, 1], [0, 2, 2]
[2, 2, 0], [2, 2, 1], [2, 2, 2]
[0, 0, 1], [1, 0, 1], [2, 0, 1]
[0, 0, 1], [0, 1, 1], [0, 2, 1]
[0, 0, 1], [1, 1, 1], [2, 2, 1]
[1, 0, 1], [1, 1, 1], [1, 2, 1]
[2, 0, 1], [1, 1, 1], [0, 2, 1]
[2, 0, 1], [2, 1, 1], [2, 2, 1]
[0, 1, 1], [1, 1, 1], [2, 1, 1]
[0, 2, 1], [1, 2, 1], [2, 2, 1]
[0, 0, 2], [1, 0, 2], [2, 0, 2]
[0, 0, 2], [0, 1, 2], [0, 2, 2]
[0, 0, 2], [1, 1, 2], [2, 2, 2]
[1, 0, 2], [1, 1, 2], [1, 2, 2]
[2, 0, 2], [1, 1, 2], [0, 2, 2]
[2, 0, 2], [2, 1, 2], [2, 2, 2]
[0, 1, 2], [1, 1, 2], [2, 1, 2]
[0, 2, 2], [1, 2, 2], [2, 2, 2]

R. H. Hardin, Table of n, a(n) for n = 1..60
Hanno Lefmann, No l Grid-Points in spaces of small dimension, Lecture Notes in Comp. Sci. 5034 (2008) 259-270 [Provides motivation]
Attilo Por and David R. Wood, No-Three-in-Line-in-3D, Algorithmica 47 (4) (2007) 481-488, [Provides motivation]
Wikipedia, No-three-in-line problem.

Cf. A178256-A178298, A178351-A178353.

# return true if xtrip1, xtrip2 and xtrip3 are three collinear points in 3D
iscolin := proc(xtrip1,xtrip2,xtrip3)
local diff21x, diff21y, diff21z, diff31x, diff31y, diff31z ;
# build the difference vectors diff2=xtrip2-xtrip1 and diff3=xtrip3-xtrip1
# and test whether diff2=t*diff3 with some parameter t
diff21x := xtrip2[1]-xtrip1[1] ;
diff21y := xtrip2[2]-xtrip1[2] ;
diff21z := xtrip2[3]-xtrip1[3] ;
diff31x := xtrip3[1]-xtrip1[1] ;
diff31y := xtrip3[2]-xtrip1[2] ;
diff31z := xtrip3[3]-xtrip1[3] ;
if xtrip1 = xtrip2 or xtrip2 = xtrip3 or xtrip1 = xtrip3 then
error("degen triple") ;
end if ;
# is diff31[] = t * diff21[] ?
if diff21x = 0 then
if diff31x = 0 then
# both difference vectors in the y-z plane
if diff21y = 0 then
if diff31y = 0 then
# both diff vects on the z-axis
return true;
else
# one on the z-axis, the other not
return false;
end if;
else
if diff31y = 0 then
# one on the z-axis, the other one not
return false;
else
# general directions in the y-z plane
t := diff31y/diff21y ;
if t*diff21z = diff31z then
return true ;
else
return false;
end if;
end if;
end if;
else
# one diff vector in the y-z plane, the other not
return false;
end if;
else
if diff31x = 0 then
# one diff vector in the y-z plane, the other not
return false;
else
t := diff31x/diff21x ;
if t*diff21y = diff31y and t*diff21z = diff31z then
return true;
else
return false;
end if;
end if;
end if;
end proc:
# convert a number n=0,1,2,3,... into a triple [n1,n2,n3], all 0<=niA000938: the number of collinear triples in n X n X n
num3in := proc(n)
local a,ncub,nlin1,nlin2,xtrip2,xtrip3 ;
a := 0 ;
ncub := n^3 ;
# linearized index of first point
for nlin1 from 0 to ncub-1 do
xtrip1 := linidx(nlin1,n) ; # [x,y,z], 0<=x,y,z

Terms a(7) onwards from R. H. Hardin, May 21 2010

Replaced an invalid reference by Wikipedia and converted others to URL's R. J. Mathar, Jun 21 2010

A189413 Number of convex quadrilaterals on an n X n grid (or geoboard).

Original entry on oeis.org

0, 1, 70, 1038, 7398, 35727, 130768, 400116, 1062016, 2531001, 5529310, 11272710, 21639022, 39559591, 69283632, 116910052, 190977408, 303286461, 469431366, 710400658, 1053055398, 1532253131, 2192246528, 3088876728, 4290532688, 5882825641, 7969711934, 10677299074, 14156978846, 18591603883, 24195121104

Offset: 1

Martin Renner, Apr 21 2011

nonn

If four points are chosen at random from an n X n grid, the probability that they form a convex quadrilateral approaches 25/36 as n increases, by Sylvester's Four-Point Theorem (see the link). Thanks to Ed Pegg Jr for this comment. - N. J. A. Sloane, Jun 15 2020

Tom Duff, Table of n, a(n) for n = 1..192
Tom Duff, Data for tables A334708, A334709, A334710, A334711 for grids of size up to 192 X 192.
Nathaniel Johnston, C program for computing terms.
Eric Weisstein's World of Mathematics, Convex Polygon.
Eric Weisstein's World of Mathematics, Quadrilateral.
Eric Weisstein's World of Mathematics, Sylvester's Four-Point Problem.

Cf. A175383, A178256, A181944, A189345, A189412, A189414.

This is the main diagonal of A334711.

a(6) - a(22) from Nathaniel Johnston, Apr 25 2011

Terms beyond a(22) from Tom Duff. - N. J. A. Sloane, Jun 23 2020

A175383 Number of complete quadrangles on an n X n grid (or geoplane).

Original entry on oeis.org

0, 1, 78, 1278, 9498, 47331, 175952, 545764, 1461672, 3507553, 7701638, 15773526, 30375194, 55695587, 97777392, 165310348, 270478344, 430196181, 666685134, 1010083690, 1498720098, 2182544223

Offset: 1

Martin Renner, Apr 19 2011

nonn

A complete quadrangle is a set of four points, no three collinear, and the six lines which join them.

Number of ways to arrange 4 indistinguishable points on an n X n square grid so that no three points are collinear at any angle. Column 4 of A194193. - R. H. Hardin, Aug 18 2011

			From _R. H. Hardin_, Aug 18 2011: (Start)
Some solutions for 3 X 3:
  0 1 1   1 1 0   1 0 1   0 1 1   0 0 0   1 1 0   1 1 0
  1 0 0   0 0 0   1 0 0   1 1 0   1 1 0   0 0 1   1 0 0
  1 0 0   1 0 1   0 0 1   0 0 0   0 1 1   0 1 0   0 1 0
(End)

R. H. Hardin, Table of n, a(n) for n = 1..55
Eric Weisstein's World of Mathematics, Complete Quadrangle.

a(n) = A189345(n) - A189346(n) - A178256(n).

a(n) = (1/3)*A189412(n) + A189413(n).

a(6)-a(22) from Nathaniel Johnston, Apr 25 2011

a(7)-a(22) corrected by Nathaniel Johnston, based on another correction by Michal Forišek, Sep 06 2011

A334708 Array read by antidiagonals: T(n,k) (n>=1, k>=1) = number of ways to select four collinear points from an n X k grid.

Original entry on oeis.org

0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 5, 2, 0, 2, 5, 15, 10, 3, 3, 10, 15, 35, 30, 15, 10, 15, 30, 35, 70, 70, 45, 29, 29, 45, 70, 70, 126, 140, 105, 72, 64, 72, 105, 140, 126, 210, 252, 210, 157, 129, 129, 157, 210, 252, 210, 330, 420, 378, 302, 248, 234, 248, 302, 378, 420, 330

Offset: 1

N. J. A. Sloane, Jun 15 2020

Computed by Tom Duff, Jun 15 2020

			The initial rows of the array are:
0, 0, 0, 1, 5, 15, 35, 70, 126, 210, 330, 495, ...
0, 0, 0, 2, 10, 30, 70, 140, 252, 420, 660, 990, ...
0, 0, 0, 3, 15, 45, 105, 210, 378, 630, 990, 1485, ...
1, 2, 3, 10, 29, 72, 157, 302, 531, 874, 1361, 2028, ...
5, 10, 15, 29, 64, 129, 248, 442, 747, 1196, 1825, 2679, ...
15, 30, 45, 72, 129, 234, 405, 666, 1065, 1638, 2439, 3510, ...
35, 70, 105, 157, 248, 405, 660, 1020, 1545, 2276, 3283, 4605, ...
70, 140, 210, 302, 442, 666, 1020, 1524, 2220, 3154, 4412, 6030, ...
126, 252, 378, 531, 747, 1065, 1545, 2220, 3156, 4362, 5940, 7923, ...
210, 420, 630, 874, 1196, 1638, 2276, 3154, 4362, 5928, 7914, 10350, ...
...
The initial antidiagonals are:
0
0, 0
0, 0, 0
1, 0, 0, 1
5, 2, 0, 2, 5
15, 10, 3, 3, 10, 15
35, 30, 15, 10, 15, 30, 35
70, 70, 45, 29, 29, 45, 70, 70
126, 140, 105, 72, 64, 72, 105, 140, 126
210, 252, 210, 157, 129, 129, 157, 210, 252, 210
330, 420, 378, 302, 248, 234, 248, 302, 378, 420, 330
...

Tom Duff, Data for tables A334708, A334709, A334710, A334711 for grids of size up to 192 X 192

The main diagonal is A178256.
Triangles A334708, A334709, A334710, A334711 give the counts for the four possible arrangements of four points.
For three points there are just two possible arrangements: see A334704 and A334705.

A189346 Number of sets of four points on an n X n grid (or geoboard), exactly three of which are collinear.

Original entry on oeis.org

0, 0, 48, 532, 3088, 11340, 33824, 83288, 183344, 364304, 681872, 1194100, 1992976, 3182332, 4941360, 7420640, 10874720, 15539952, 21812720, 30011924, 40650368, 54187196, 71463440, 92990296, 119675712, 152314920, 192393872, 240690060

Offset: 1

Martin Renner, Apr 20 2011

nonn

The four points build a triangle on an n X n grid, with one of them located on a side of the triangle.

The number of sets of four points with the three collinear points in a horizontal or vertical line is 2*n^2*(n-1)*binomial(n,3) = 4*A090448(n). The number of sets of four points with the three collinear points in a diagonal line of slope 1 is 2*n*(n-1)*binomial(n,3) + 4*Sum_{k=3..n-1}(n^2-k)*binomial(k,3). The sum of these two values is a lower bound for this sequence. - Nathaniel Johnston, Apr 23 2011

Martin Renner, Table of n, a(n) for n = 1..76

Cf. A000938, A175383, A178256, A189345.

A189346 := proc(n)local a,b,j,k,l,m,s,slopes,num,den,tot: tot := 0: slopes := {}: for b from 1 to ceil(n/2)-1 do for a from 0 to b do slopes := slopes union {a/b}: od: od: for s from 1 to nops(slopes) do num := numer(slopes[s]): den := denom(slopes[s]): if(num = 0)then tot := tot + 2*n^2*(n-1)*binomial(n,3): elif(num = den)then tot := tot + 2*(2*add(binomial(k,3)*(n^2-k), k=3..n) - binomial(n,3)*(n^2 - n)): else for j from 1 to n - 2*den do for k from 1 to n - 2*num do tot := tot + 4*(n^2 - 3): for l from 1 to n do for m from 1 to n do if((not l = j or not m = k) and (not l = j + den or not m = k + num) and (not l = j + 2*den or not m = k + 2*num) and (m - k)*den = num*(l - j))then tot := tot - 4: fi: od: od: od: od: fi: od: return tot: end:
seq(A189346(n),n=1..15); # Nathaniel Johnston, Apr 23 2011

a(6)-a(28) from Nathaniel Johnston, Apr 23 2011

cp's OEIS Frontend

A157882 Number of collinear point-triples in the n X n X n cube.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Extensions

A189413 Number of convex quadrilaterals on an n X n grid (or geoboard).

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A175383 Number of complete quadrangles on an n X n grid (or geoplane).

Views

Author

Keywords

Comments

Examples

Links

Formula

Extensions

A334708 Array read by antidiagonals: T(n,k) (n>=1, k>=1) = number of ways to select four collinear points from an n X k grid.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A189346 Number of sets of four points on an n X n grid (or geoboard), exactly three of which are collinear.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions