login
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
OFFSET
1,2
FORMULA
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)
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.
Sequence in context: A143666 A139757 A285918 * A296363 A164603 A229714
KEYWORD
nonn,easy
AUTHOR
Ran Pan, Sep 21 2015
EXTENSIONS
Terms corrected and entry revised by N. J. A. Sloane, Dec 16 2017 following an email from Jared Nash, Dec 14 2017.
STATUS
approved