A262402 a(n) = number of triangles that can be formed from the points of a 3 X n grid.
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
Links
- 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).
Crossrefs
Programs
-
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 *) -
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
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)
Extensions
Terms corrected and entry revised by N. J. A. Sloane, Dec 16 2017 following an email from Jared Nash, Dec 14 2017.