A296367 -id:A296367 - 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

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.

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

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