A045996 -id:A045996 - cp's OEIS frontend

A190019 Number of acute triangles on an n X n grid (or geoboard).

0, 0, 8, 80, 404, 1392, 3880, 9208, 19536, 38096, 69288, 119224, 196036, 310008, 474336, 705328, 1023216, 1451904, 2020232, 2762848, 3719420, 4937200, 6469424, 8378184, 10734664, 13618168, 17119288, 21338760, 26390452, 32400592, 39508656, 47870200, 57655752

Offset: 1

Martin Renner, May 04 2011

nonn

Place all bounding boxes of A280653 that will fit into the n X n grid in all possible positions, and the proper rectangles in two orientations: a(n) = Sum_{i=1..n} Sum_{j=1..i} k * (n-i+1) * (n-j+1) * A280653(i,j) where k=1 when i=j and k=2 otherwise. - Lars Blomberg, Feb 26 2017

According to Langford (p. 243), the leading order is (53/150-Pi/40)*C(n^2,3). See A093072. - Michael R Peake, Jan 15 2021

Lars Blomberg, Table of n, a(n) for n = 1..5000
Margherita Barile, Geoboard.
Eric Langford, A problem in geometric probability, Mathematics Magazine, Nov-Dec, 1970, 237-244.
Eric Weisstein's World of Mathematics, Acute Triangle.

Cf. A045996, A077435, A093072, A280653.

Cf. A103429 (analogous problem on a 3-dimensional grid).

a(n) = A045996(n) - A077435(n) - A190020(n).

Extended by Ray Chandler, May 04 2011

More terms from Lars Blomberg, Feb 26 2017

A190020 Number of obtuse triangles on an n X n grid (or geoboard).

Original entry on oeis.org

0, 0, 24, 236, 1148, 3932, 10760, 25392, 53576, 103824, 188104, 322852, 529116, 835028, 1275360, 1893496, 2742208, 3886568, 5402448, 7381316, 9928860, 13168484, 17243896, 22319864, 28579720, 36237928, 45532720, 56732668

Offset: 1

Martin Renner, May 04 2011

nonn

Place all bounding boxes of A280652 that will fit into the n X n grid in all possible positions, and the proper rectangles in two orientations: a(n) = Sum_{i=1..n} Sum_{j=1..i} k * (n-i+1) * (n-j+1) * A280652(i,j) where k=1 when i=j and k=2 otherwise. - Lars Blomberg, Mar 02 2017

According to Langford (p. 243), the leading order is (97/150 + Pi/40)*C(n^2,3). See A093072. - Michael R Peake, Jan 15 2021

Lars Blomberg, Table of n, a(n) for n = 1..10000
Margherita Barile, MathWorld -- Geoboard.
Eric Langford, A problem in geometric probability, Mathematics Magazine, Nov-Dec, 1970, 237-244.
Eric Weisstein's World of Mathematics, Obtuse Triangle.

Cf. A045996, A077435, A093072, A190019, A280652.

a(n) = A045996(n) - A077435(n) - A190019(n).

Extended by Ray Chandler, May 04 2011

A235454 Number of non-equivalent (mod D_4) ways to arrange 3 points on an n X n square grid so that they are not collinear.

Original entry on oeis.org

1, 13, 70, 290, 867, 2266, 5068, 10475, 19764, 35406, 59817, 97375, 152154

Offset: 2

Heinrich Ludwig, Jan 12 2014

Column 3 of A235453.
Also number of non-equivalent triangles in an n X n grid.
Without the restriction "non-equivalent (mod D_4)" the numbers are given by A045996, n >= 2.

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

Cf. A235453, A045996, A235455 (4 points), A235456 (5 points), A235457 (6 points), A235458 (7 points).

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

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

A178208 Number of ways to choose three points in an (n X n)-grid (or geoplane).

Original entry on oeis.org

0, 4, 84, 560, 2300, 7140, 18424, 41664, 85320, 161700, 287980, 487344, 790244, 1235780, 1873200, 2763520, 3981264, 5616324, 7775940, 10586800, 14197260, 18779684, 24532904, 31684800, 40495000, 51257700, 64304604, 80007984, 98783860, 121095300, 147455840, 178433024

Offset: 1

Martin Renner, May 22 2010

Index entries for linear recurrences with constant coefficients, signature (7,-21,35,-35,21,-7,1).

Cf. A045996, A000938.

Binomial[Range[30]^2, 3] (* or *) LinearRecurrence[{7,-21,35,-35,21,-7,1},{0,4,84,560,2300,7140,18424},30] (* Harvey P. Dale, Nov 09 2012 *)

a(n)=binomial(n^2,3) \\ Charles R Greathouse IV, Feb 19 2017

a(n) = A000938(n) + A045996(n).
a(n) = binomial(n^2,3) = 1/6*n^2*(n^2-1)*(n^2-2). - Martin Renner, May 23 2010
G.f.: 4*x^2*(1+x)*(1+13*x+x^2)/(1-x)^7. - Colin Barker, Jan 19 2012
a(1)=0, a(2)=4, a(3)=84, a(4)=560, a(5)=2300, a(6)=7140, a(7)=18424, a(n)=7*a(n-1)-21*a(n-2)+35*a(n-3)-35*a(n-4)+21*a(n-5)-7*a(n-6)+a(n-7). - Harvey P. Dale, Nov 09 2012
Sum_{n>=2} 1/a(n) = Pi^2/2 - 15/4 - 3*Pi*cot(sqrt(2)*Pi)/(2*sqrt(2)). - Amiram Eldar, Feb 17 2024

Extended by Ray Chandler, May 03 2011

Corrected by Harvey P. Dale, Nov 09 2012

A262402 a(n) = number of triangles that can be formed from the points of a 3 X n grid.

Original entry on oeis.org

0, 18, 76, 200, 412, 738, 1200, 1824, 2632, 3650, 4900, 6408, 8196, 10290, 12712, 15488, 18640, 22194, 26172, 30600, 35500, 40898, 46816, 53280, 60312, 67938, 76180, 85064, 94612, 104850, 115800, 127488, 139936, 153170, 167212, 182088, 197820, 214434, 231952, 250400, 269800, 290178, 311556

Offset: 1

Ran Pan, Sep 21 2015

Andrew Howroyd, Table of n, a(n) for n = 1..1000
Jared Nash, Formula for number of triangles in a 3 X n grid
Ran Pan, Exercise T, Project P, 2015.
Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).

Cf. A115514, A045996, A296367.

The old, incorrect, formula proposed for this problem is now in A296363.

A:=n-> if n mod 2 = 0 then n^2*(8*n-7)/2 else n^2*(8*n-7)/2-1/2; fi; [seq(A(n),n=1..30)]; # N. J. A. Sloane, Dec 16 2017

LinearRecurrence[{3, -2, -2, 3, -1}, {0, 18, 76, 200, 412}, 50] (* Jean-François Alcover, Aug 26 2019 *)

concat(0, Vec(2*x^2*(9 + 11*x + 4*x^2) / ((1 - x)^4*(1 + x)) + O(x^40))) \\ Colin Barker, Dec 20 2017

a(n) = n^2*(8*n-7)/2 - (n mod 2)/2. - Jared Nash, Dec 14 2017
Proof of Jared Nash's formula, from N. J. A. Sloane, Dec 16 2017 (Start).
On a 3Xn grid of points, a triangle can either have 2 points on one line and 1 point on another line (for a total of 6*n*binomial(n,2) ways) or one point on each line (in n^3 - Q ways, where Q is the number of degenerate triangles formed by collinear triples with one point on each line).
Q is equal to n (for vertical triples) plus 2*floor((n-1)^2/4) (since a downward-sloping diagonal passing through the points (1,i), (2,i+d), (3,i+2d), say, where i >= 1, i+2d <= n, can be drawn in Sum_{i=1..n-2} floor((n-i)/2) ways, and this sum is equal to floor((n-1)^2/4), as can be seen by considering the row sums of the triangle A115514).
So a(n) = 6*n*binomial(n,2) + n^3 - (n + 2*floor((n-1)^2/4)), which simplifies to give the above formula. (End)
For another proof, see the link.
G.f.: 2*x^2*(4*x^2 + 11*x + 9) / ((1 - x)^3*(1 - x^2)). - N. J. A. Sloane, Dec 16 2017
From Colin Barker, Dec 20 2017: (Start)
a(n) = n^2*(8*n - 7) / 2 for n even.
a(n) = (8*n^3 - 7*n^2 - 1) / 2 for n odd.
a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5) for n>5.
(End)

Terms corrected and entry revised by N. J. A. Sloane, Dec 16 2017 following an email from Jared Nash, Dec 14 2017.

A296367 Number of triangles on a 4 X n grid.

Original entry on oeis.org

0, 48, 200, 516, 1056, 1884, 3052, 4628, 6668, 9232, 12380, 16176, 20672, 25936, 32024, 38996, 46912, 55836, 65820, 76932, 89228, 102768, 117612, 133824, 151456, 170576, 191240, 213508, 237440, 263100, 290540, 319828, 351020, 384176, 419356, 456624, 496032, 537648, 581528, 627732, 676320

Offset: 1

Jared Nash and N. J. A. Sloane, Dec 19 2017, corrected Dec 23 2017

Colin Barker, Table of n, a(n) for n = 1..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,-1,0,2,-1).

Cf. A001840, A045996, A115514, A262402.

A:=proc(n)
6*n^2*(n-1)
+ 2*(n^3 - n - 2*floor((n-1)^2/4))
+ 2*(n^3 - n - 2*floor((n-1)*(n-2)/6));
end;
[seq(A(n),n=1..64)];

concat(0, Vec(4*x^2*(12 + 26*x + 29*x^2 + 18*x^3 + 5*x^4) / ((1 - x)^4*(1 + x)*(1 + x + x^2)) + O(x^40))) \\ Colin Barker, Dec 26 2017

a(n) = 2*n*(n-1)*(5*n+2) - 4*floor((n-1)^2/4) - 4*floor((n-1)*(n-2)/6).
Proof: We will show that a(n) = 6*n^2*(n-1) + 2*(n^3 - n - 2*floor((n-1)^2/4)) + 2*(n^3 - n - 2*floor((n-1)*(n-2)/6)), which is equivalent to the above formula. The argument is similar to that used to prove the formula for A262402.
There are three cases. On a 4Xn grid of points, a triangle can either have (I) 2 points on one line and 1 point on another line, (II) one point on each of lines 1,2,3 or 2,3,4, or (III) one point on each of lines 1,2,4 or 1,3,4.
(I) The triangle can be drawn in 4*3*binomial(n,2)*n = 6*n^2*(n-1) ways.
(II) Suppose the points are on lines 1,2,3. The number of triangles is n^3 - Q, where Q is the number of degenerate triangles formed by collinear triples with one point on each of lines 1,2,3. Q is equal to n (for vertical triples) plus 2*floor((n-1)^2/4) (since a downward-sloping diagonal passing through the points (1,i), (2,i+d), (3,i+2d), say, where i >= 1, d >= 1, i+2d <= n, can be drawn in Sum_{i=1..n-2} floor((n-i)/2) ways, and this sum is equal to floor((n-1)^2/4), as can be seen by considering the row sums of the triangle A115514). So in the "1,2,3" case the number of triangles is n^3 - n - 2*floor((n-1)^2/4). The same number arises in the "2,3,4" case.
(III) Suppose the points are on lines 1,2,4. The number of triangles is n^3 - Q, where Q is the number of degenerate triangles formed by collinear triples with one point on each of lines 1,2,4.  There are n vertical triples. If the three points are on a downward sloping line, through points (1,i), (2,i+d, i+3d), say, with i >= 1, d >= 1, i+3d <= n, there are Sum_{i=1..n-2} floor((n-i)/2) possibilities, and this sum is equal to floor((n-1)*(n-2)/6) (see A001840). So in this case there are n^3 - n - 2*floor((n-1)*(n-2)/6) triangles. The same number arises in the "1,3,4" case. QED.
G.f.: 4*x^2*(5*x^4+18*x^3+29*x^2+26*x+12)/((1-x)^2*(1-x^2)*(1-x^3)).
a(n) = 2*a(n-1) - a(n-3) - a(n-4) + 2*a(n-6) - a(n-7) for n>7. - Colin Barker, Dec 26 2017

A372915 a(n) is the number of distinct triangles with area n whose vertices are points of an n X n grid.

Original entry on oeis.org

0, 0, 2, 4, 9, 10, 25, 22, 38, 49, 56, 56, 111, 71, 119, 141, 153, 126, 249, 166, 244, 299, 279, 244, 463, 288, 361, 489, 517, 373, 677, 436, 626, 719, 620, 665, 1078, 604, 811, 936, 1000, 749, 1444, 842, 1221, 1384, 1173, 1016, 1871, 1261, 1393, 1597, 1566, 1259

Offset: 0

Felix Huber, Jun 02 2024

nonn

			See the linked illustration for the term a(4) = 9.

Felix Huber, Table of n, a(n) for n=0..666
Felix Huber, Illustration of the term a(4) = 9

Cf. A045996, A088658, A303331, A320310, A320542, A320544, A334713, A372217, A372218.

A372915:=proc(n)
  local p,q,g,h,u,v,x,y,L,M;
  L:=[];
  for g from 2 to n do
    h:=2*n/g;
    if type(h,integer) then
      for x to n do
        M:=[g,sqrt(x^2+h^2),sqrt((g-x)^2+h^2)];
        M:=sort(M);
        if not member(M,L) then
          L:=[op(L),M];
        fi;
      od;
    fi;
  od;
  for p to n do
    for q from 1 to p do
      g:=sqrt(p^2+q^2);
      h:=2*n/g;
      u:=h/g*q;
      v:=q+h/g*p;
      for x from max(1,ceil(p/q*(v-n)+u)) to min(n,floor(p/q*v+u)) do
        y:=q/p*(u-x)+v;
        if type(y,integer) and x <> p and y <> q then
          M:=[g,sqrt(x^2+(y-q)^2),sqrt((x-p)^2+y^2)];
          M:=sort(M);
          if not member(M,L) then
            L:=[op(L),M];
          fi;
        fi;
      od;
    od;
  od;
  return numelems(L);
end proc;
seq(A372915(n),n=0..53);

A190312 Number of scalene triangles on an n X n grid (or geoboard).

Original entry on oeis.org

0, 0, 40, 368, 1704, 5704, 15400, 36096, 75632, 145968, 263592, 451392, 738360, 1163552, 1774840, 2632344, 3808992, 5394752, 7493936, 10233832, 13759008, 18241312, 23877984, 30896984, 39551456, 50137240, 62983128, 78459880

Offset: 1

Martin Renner, May 08 2011

nonn

Eric Weisstein's World of Mathematics, Geoboard.
Eric Weisstein's World of Mathematics, Scalene Triangle.

Cf. A045996, A186434.

q[n_] :=
  Module[{sqDist, t0, t1, t2},
   (* Squared distances *)
   sqDist = {p_, q_} :> (Floor[p/n] - Floor[q/n])^2 + (Mod[p, n] - Mod[q, n])^2;
   (* Triads of points *)
   t0 = Subsets[Range[0, n^2 - 1], {3, 3}];
   (* Exclude collinear vertices *)
   t1 = Select[t0, Det[Map[{Floor[#/n], Mod[#, n], 1} &, {#[[1]], #[[2]], #[[
           3]]}]] != 0 &];
   (* Calculate sides *)
   t2 = Map[{#,
    Sort[{{#[[2]], #[[3]]}, {#[[3]], #[[1]]}, {#[[1]], #[[2]]}} /. sqDist]}&, t1];
   (* Select scalenes *)
   t2 = Select[t2,
      #[[2, 1]] != #[[2, 2]] && #[[2, 2]] != #[[2, 3]] && #[[2,3]] != #[[2, 1]] &];
   Return[Length[t2]];
   ];
Map[q[#] &, Range[9]] (* César Eliud Lozada, Mar 26 2021 *)

a(n) = A045996(n) - A186434(n).

A358532 a(n) is the row position of the next open point in the structure generated by adding the largest diamond possible at the next open point on a triangular grid of side n. See Comments and Example sections for more details.

Original entry on oeis.org

1, 1, 2, 1, 2, 3, 1, 4, 1, 3, 7, 1, 3, 6, 4, 10, 1, 9, 4, 7, 9, 5, 14, 1, 11, 5, 7, 8, 11, 14, 19, 1, 6, 6, 24, 9, 14, 20, 1, 8, 8, 8, 20, 8, 19, 24, 30, 15, 19, 19, 19, 27, 1, 19, 15, 16, 20, 28, 8, 39, 11, 24, 1, 11, 16, 26, 28, 29, 30, 39, 50, 20, 31, 32, 33

Offset: 1

John Tyler Rascoe, Nov 20 2022

A structure of diamonds is built up successively by adding the largest possible diamond to the next open point within a triangular grid of side n. Each new diamond is added to the preceding structure of diamonds. At each step n, a new row of n open points is first added, extending the triangular grid.
Then the next open point is defined as the first open point encountered when the triangle is read by rows starting from the top row. a(n) is then the row position of the next open point.
Finally, starting at this open point the largest diamond that does not overlap any previous diamonds and fits within the triangular grid is added. Each diamond of side length k must cover exactly k^2 points, with the top corner on an open point. The points covered by the added diamond are then considered closed.
Is there a pattern for the values of n where a(n) = 1?

			Here zeros are the open points; closed points covered by the n-th diamond are replaced with n.
  ---------------------
  n=4       1          First a new row of 4 open points is added.
           2 3         Then the next open point is T(3,1) so a(4) = 1.
          4 0 0        Finally, the largest diamond fitting at T(3,1) is 1.
         0 0 0 0
  ---------------------
  n=5       1          First a new row of 5 open points is added.
           2 3         Then the next open point is T(3,2) so a(5) = 2.
          4 5 0        Finally, the largest diamond fitting at T(3,2) is 2.
         0 5 5 0
        0 0 5 0 0
  ---------------------
  n=6       1          First a new row of 6 open points is added.
           2 3         Then the next open point is T(3,3) so a(6) = 3.
          4 5 6        Finally, the largest diamond fitting at T(3,3) is 1.
         0 5 5 0
        0 0 5 0 0
       0 0 0 0 0 0

John Tyler Rascoe, Table of n, a(n) for n = 1..10000
John Tyler Rascoe, Python program

Cf. A045996, A186434, A194136, A239567, A279413.

Python
```
# see linked program
```

cp's OEIS Frontend

A190019 Number of acute triangles on an n X n grid (or geoboard).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A190020 Number of obtuse triangles on an n X n grid (or geoboard).

Views

Author

Keywords

Comments

Links

Crossrefs

Formula

Extensions

A235454 Number of non-equivalent (mod D_4) ways to arrange 3 points on an n X n square grid so that they are not collinear.

Views

Author

Keywords

Comments

Examples

Crossrefs

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

A178208 Number of ways to choose three points in an (n X n)-grid (or geoplane).

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A262402 a(n) = number of triangles that can be formed from the points of a 3 X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A296367 Number of triangles on a 4 X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A372915 a(n) is the number of distinct triangles with area n whose vertices are points of an n X n grid.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

A190312 Number of scalene triangles on an n X n grid (or geoboard).

Views

Author