|
|
A262402
|
|
a(n) = number of triangles that can be formed from the points of a 3 X n grid.
|
|
4
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = n^2*(8*n-7)/2 - (n mod 2)/2. - Jared Nash, Dec 14 2017
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
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)
|
|
MAPLE
|
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
|
|
MATHEMATICA
|
LinearRecurrence[{3, -2, -2, 3, -1}, {0, 18, 76, 200, 412}, 50] (* Jean-François Alcover, Aug 26 2019 *)
|
|
PROG
|
(PARI) 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
|
|
CROSSREFS
|
The old, incorrect, formula proposed for this problem is now in A296363.
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|