A262402 -id:A262402 - cp's OEIS frontend

A334705 Triangle read by rows: T(n,k) (1 <= k <= n) = number of ways to choose three points from an n X k grid of points which are the vertices of a triangle of nonzero area.

0, 0, 4, 0, 18, 76, 0, 48, 200, 516, 0, 100, 412, 1056, 2148, 0, 180, 738, 1884, 3820, 6768, 0, 294, 1200, 3052, 6176, 10922, 17600, 0, 448, 1824, 4628, 9352, 16516, 26588, 40120, 0, 648, 2632, 6668, 13456, 23740, 38192, 57588, 82608, 0, 900, 3650, 9232, 18612, 32812, 52758, 79508, 114000, 157252

Offset: 1

N. J. A. Sloane, Jun 13 2020

It follows from the definitions that T(n,k) + A334704(n,k) = A334703(n,k) for 1 <= k <= n.

			Triangle begins:
0,
0, 4,
0, 18, 76,
0, 48, 200, 516,
0, 100, 412, 1056, 2148,
0, 180, 738, 1884, 3820, 6768,
0, 294, 1200, 3052, 6176, 10922, 17600,
0, 448, 1824, 4628, 9352, 16516, 26588, 40120,
0, 648, 2632, 6668, 13456, 23740, 38192, 57588, 82608,
0, 900, 3650, 9232, 18612, 32812, 52758, 79508, 114000, 157252,
0, 1210, 4900, 12380, 24940, 43934, 70608, 106364, 152456, 210234, 280988,
...
This is the lower half of a symmetric array. The full symmetric array begins:
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, ...
0, 4, 18, 48, 100, 180, 294, 448, 648, 900, 1210, 1584, ...
0, 18, 76, 200, 412, 738, 1200, 1824, 2632, 3650, 4900, 6408, ...
0, 48, 200, 516, 1056, 1884, 3052, 4628, 6668, 9232, 12380, 16176, ...
0, 100, 412, 1056, 2148, 3820, 6176, 9352, 13456, 18612, 24940, 32568, ...
0, 180, 738, 1884, 3820, 6768, 10922, 16516, 23740, 32812, 43934, 57336, ...
0, 294, 1200, 3052, 6176, 10922, 17600, 26588, 38192, 52758, 70608, 92112, ...
0, 448, 1824, 4628, 9352, 16516, 26588, 40120, 57588, 79508, 106364, 138708, ...
0, 648, 2632, 6668, 13456, 23740, 38192, 57588, 82608, 114000, 152456, 198760, ...
0, 900, 3650, 9232, 18612, 32812, 52758, 79508, 114000, 157252, 210234, 274016 , ...
0, 1210, 4900, 12380, 24940, 43934, 70608, 106364, 152456, 210234, 280988, 366152, ...
...

This is a companion to the triangles A334703 and A334704.

Rows (or columns) 2,3,4,5 of the full array are A045991, A262402, A296367, A334707. The main diagonal is A045996.

Rows 6 onwards from Tom Duff (see the Duff link in A334704). - N. J. A. Sloane, Jun 19 2020

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

A296363 a(1)=0; for n>1, a(n) = 4n^3 - 3n^2 - 3*n + 4.

Original entry on oeis.org

0, 18, 76, 200, 414, 742, 1208, 1836, 2650, 3674, 4932, 6448, 8246, 10350, 12784, 15572, 18738, 22306, 26300, 30744, 35662, 41078, 47016, 53500, 60554, 68202, 76468, 85376, 94950, 105214, 116192, 127908, 140386, 153650, 167724, 182632, 198398, 215046, 232600

Offset: 1

N. J. A. Sloane, Dec 16 2017

This was once thought (mistakenly) to be a formula for A262402.

Peter Kagey, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (4, -6, 4, -1).

Cf. A262402.

[0] cat [4*n^3-3*n^2-3*n+4: n in [2..40]]; // Vincenzo Librandi, Sep 23 2015

CoefficientList[Series[- 2 x (x^3 - 2 x^2 - 2 x - 9)/(x - 1)^4, {x, 0, 30}], x] (* Vincenzo Librandi, Sep 23 2015 *)
Join[{0},LinearRecurrence[{4, -6, 4, -1},{18, 76, 200, 414},38]] (* Ray Chandler, Sep 23 2015 *)
Join[{0},Table[4n^3-3n^2-3n+4,{n,2,40}]] (* Harvey P. Dale, Mar 28 2019 *)

a(n)=if(n>1, 4*n^3 - 3*n^2 - 3*n + 4, 0) \\ Charles R Greathouse IV, Oct 18 2022

G.f.: -2 * (x^3-2*x^2-2*x-9) * x^2 / (x-1)^4.

cp's OEIS Frontend

A334705 Triangle read by rows: T(n,k) (1 <= k <= n) = number of ways to choose three points from an n X k grid of points which are the vertices of a triangle of nonzero area.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A296367 Number of triangles on a 4 X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A296363 a(1)=0; for n>1, a(n) = 4n^3 - 3n^2 - 3*n + 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

cp's OEIS Frontend

A334705 Triangle read by rows: T(n,k) (1 <= k <= n) = number of ways to choose three points from an n X k grid of points which are the vertices of a triangle of nonzero area.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A296367 Number of triangles on a 4 X n grid.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

PARI

Formula

A296363 a(1)=0; for n>1, a(n) = 4*n^3 - 3*n^2 - 3*n + 4.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A296363 a(1)=0; for n>1, a(n) = 4n^3 - 3n^2 - 3*n + 4.