A175383 -id:A175383 - cp's OEIS frontend

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

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

A279438 Number of ways to place 4 points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Original entry on oeis.org

0, 1, 90, 1428, 10600, 51525, 190806, 584080, 1552608, 3701025, 8088850, 16470036, 31616520, 57743413, 101055150, 170433600, 278290816, 441610785, 683206218, 1033218100, 1530887400, 2226630021, 3184447750, 4484709648, 6227340000, 8535450625, 11559457026, 15481719540

Offset: 1

Heinrich Ludwig, Dec 12 2016

Column 5 of triangle A279445.
Rotations and reflections of placements are counted. For numbers if they are to be ignored see A279448.
For condition "no more than 2 points on straight lines at any angle", see A175383.

Heinrich Ludwig, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1).

Cf. A175383, A249448, A279444, A279445, A197458.

Same problem but 2,3,5..9 points: A083374, A279437, A279439, A279440, A279441, A279442, A279443.

Table[(n^8 - 14 n^6 + 30 n^5 - 17 n^4 - 6 n^3 + 6 n^2)/24, {n, 28}] (* Michael De Vlieger, Dec 12 2016 *)
LinearRecurrence[{9,-36,84,-126,126,-84,36,-9,1},{0,1,90,1428,10600,51525,190806,584080,1552608},30] (* Harvey P. Dale, Sep 05 2024 *)

concat(0, Vec(x^2*(1 + 81*x + 654*x^2 + 904*x^3 + 99*x^4 - 57*x^5 - 2*x^6) / (1 - x)^9 + O(x^30))) \\ Colin Barker, Dec 13 2016

a(n) = (n^6 - 14*n^4 + 30*n^3 - 17*n^2 - 6*n + 6)*n^2/24 \\ Charles R Greathouse IV, Dec 13 2016

a(n) = (n^8 - 14*n^6 + 30*n^5 - 17*n^4 - 6*n^3 + 6*n^2)/24.
a(n) = 9*a(n-1) - 36*a(n-2) + 84*a(n-3) - 126*a(n-4) + 126*a(n-5) - 84*a(n-6) + 36*a(n-7) - 9*a(n-8) + a(n-9).
G.f.: x^2*(1 + 81*x + 654*x^2 + 904*x^3 + 99*x^4 - 57*x^5 - 2*x^6) / (1 - x)^9. - Colin Barker, Dec 13 2016

A189412 Number of concave quadrilaterals on an n X n grid (or geoboard).

Original entry on oeis.org

0, 0, 24, 720, 6300, 34812, 135552, 436944, 1198968, 2929656, 6516984, 13502448, 26208516, 48407988, 85481280, 145200888, 238502808, 380729160, 591761304, 899049096, 1336994100, 1950873276, 2798226336, 3952174032, 5500597632, 7555866072, 10253438688

Offset: 1

Martin Renner, Apr 21 2011

nonn

Michal Forišek, Table of n, a(n) for n = 1..50
Eric Weisstein's World of Mathematics, Concave Polygon.
Eric Weisstein's World of Mathematics, Quadrilateral.

Cf. A175383, A189345, A189413, A189414.

def gcd(x, y):
  x, y = abs(x), abs(y)
  while y: x, y = y, x%y
  return x
def concave(N):
  V = [ (r, c) for r in range(-N+1, N) for c in range(N) if (c>0 or r>0) ]
  answer = 0
  for i in range(len(V)):
    for j in range(i):
      r1, c1, r2, c2 = V[i]+V[j]
      rr, cr, ta = N-max(r1, r2, 0)+min(r1, r2, 0), N-max(c1, c2), abs(r1*c2-r2*c1)
      if rr>0 and cr>0 and ta>0:
        answer += 3*rr*cr*(ta+2-gcd(r1, c1)-gcd(r2, c2)-gcd(r1-r2, c1-c2))/2
  return answer
for N in range(1, 28):
    print(int(concave(N)), end=', ')

a(6)-a(22) from Nathaniel Johnston, Apr 25 2011
Terms a(7)-a(22) corrected by Michal Forisek, Sep 06 2011
Terms a(23)-a(50) added by Michal Forisek, Sep 06 2011

A194193 Square array read by antidiagonals downwards: T(n,k) = number of ways to arrange k indistinguishable points on an n X n square grid so that no three points are collinear at any angle.

Original entry on oeis.org

1, 0, 4, 0, 6, 9, 0, 4, 36, 16, 0, 1, 76, 120, 25, 0, 0, 78, 516, 300, 36, 0, 0, 28, 1278, 2148, 630, 49, 0, 0, 2, 1668, 9498, 6768, 1176, 64, 0, 0, 0, 998, 25052, 47331, 17600, 2016, 81, 0, 0, 0, 204, 36698, 215448, 175952, 40120, 3240, 100, 0, 0, 0, 11, 26700, 620210

Offset: 1

R. H. Hardin, Aug 18 2011

Columns 4..7 are A175383, A194190, A194191, A194192 respectively. - Heinrich Ludwig, Nov 16 2016

			Table starts:
...1.....0.......0........0..........0...........0............0............0
...4.....6.......4........1..........0...........0............0............0
...9....36......76.......78.........28...........2............0............0
..16...120.....516.....1278.......1668.........998..........204...........11
..25...300....2148.....9498......25052.......36698........26700.........8242
..36...630....6768....47331.....215448......620210......1073076......1035097
..49..1176...17600...175952....1189868.....5367308.....15657764.....28228158
..64..2016...40120...545764....5199888....34678364....159413700....491910848
..81..3240...82608..1461672...18520572...169259212...1108580092...5122725512
.100..4950..157252..3507553...56978440...682686652...6030207624..38914424892
.121..7260..280988..7701638..155627304..2356999994..26852315940.229093733030
.144.10296..477012.15773526..388897892..7294368210.104865006648
.169.14196..775172.30375194..894254904.20227526910
.196.19110.1214768.55695587.1932504496
.225.25200.1844512.97777392
.256.32640.2725000
...
Some solutions for n=4, k=4:
..0..0..1..0....0..0..0..0....0..0..0..0....0..0..1..0....1..0..0..0
..1..0..0..0....1..0..0..0....0..0..1..0....1..0..0..0....0..0..0..1
..0..0..0..0....0..1..0..1....1..0..1..0....1..0..0..0....0..0..0..1
..0..0..1..1....0..1..0..0....0..1..0..0....0..0..0..1....1..0..0..0

R. H. Hardin and Heinrich Ludwig, Table of n, a(n) for n = 1..199, (first 181 terms from R. H. Hardin)

Column 1 is A000290.
Column 2 is A083374.
Column 3 is A045996.
Column 4 is A175383.
Column 5 is A194190.
Column 6 is A194191.
Column 7 is A194192.

A189345 Number of ways to choose four points in an n X n grid (or geoplane).

Original entry on oeis.org

0, 1, 126, 1820, 12650, 58905, 211876, 635376, 1663740, 3921225, 8495410, 17178876, 32795126, 59626385, 103962600, 174792640, 284660376, 450710001, 695946630, 1050739900, 1554599970, 2258257001, 3226076876, 4538847600, 6296972500, 8624108025, 11671285626

Offset: 1

Martin Renner, Apr 20 2011

Index entries for linear recurrences with constant coefficients, signature (9,-36,84,-126,126,-84,36,-9,1)

Cf. A175383, A189346.

a:= proc(n) binomial(n^2, 4) end: seq(a(n), n=1..35);

makelist(binomial(n^2, 4), n, 1, 56); /* Martin Ettl, Oct 15 2012 */

a(n) = binomial(n^2,4) = (1/24)*n^2*(n^2-1)*(n^2-2)*(n^2-3).

G.f.: x^2*(1+x)*(1+116*x+606*x^2+116*x^3+x^4)/(1-x)^9. - Colin Barker, Jan 19 2012

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

Original entry on oeis.org

0, 1, 94, 1758, 13698, 70539, 266320, 837060, 2260984, 5460657, 12046294, 24775158, 47847538, 87967579, 154764912, 262110940, 429480216, 684015621, 1061192670, 1609449754, 2390049498, 3483126407

Offset: 1

Martin Renner, Apr 21 2011

nonn

Eric Weisstein's World of Mathematics, Quadrilateral.

Cf. A175383, A189345, A189412, A189413.

a(n) = A189412(n) + A189413(n).

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

a(7) - a(22) corrected by Michal Forisek, Sep 06 2011

A235455 Number of non-equivalent (mod D_4) ways to arrange 4 points on an n X n square grid so that no three points are collinear.

Original entry on oeis.org

1, 15, 181, 1253, 6044, 22302, 68661, 183645, 439578, 964938, 1974128, 3801457, 6966581

Offset: 2

Heinrich Ludwig, Jan 12 2014

Column 4 of A235453.
Also number of non-equivalent complete quadrangles on an n X n grid.
Without the restriction "non-equivalent (mod D_4)" the numbers are given by A175383, n >= 2.

			There are a(3) = 15 non-equivalent ways to place 4 points (X) on a 3 X 3 grid. Examples are:
  X . X    . X .    X X .
  . . .    X . X    X . .
  X . X    . X .    . . X

Cf. A235453, A045996, A235454 (3 points), A235456 (5 points), A235457 (6 points), A235458 (7 points)

a(13), a(14) from Heinrich Ludwig, Nov 16 2016

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

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

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A279438 Number of ways to place 4 points on an n X n square grid so that no more than 2 points are on a vertical or horizontal straight line.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

PARI

Formula

A189412 Number of concave quadrilaterals on an n X n grid (or geoboard).

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Extensions

A194193 Square array read by antidiagonals downwards: T(n,k) = number of ways to arrange k indistinguishable points on an n X n square grid so that no three points are collinear at any angle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A189345 Number of ways to choose four points in an n X n grid (or geoplane).

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Maxima

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A235455 Number of non-equivalent (mod D_4) ways to arrange 4 points on an n X n square grid so that no three points are collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

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