cp's OEIS Frontend

A262402 a(n) = number of triangles that can be formed from the points of a 3 X n grid.

%I A262402 #53 Jun 13 2020 16:12:44
%S A262402 0,18,76,200,412,738,1200,1824,2632,3650,4900,6408,8196,10290,12712,
%T A262402 15488,18640,22194,26172,30600,35500,40898,46816,53280,60312,67938,
%U A262402 76180,85064,94612,104850,115800,127488,139936,153170,167212,182088,197820,214434,231952,250400,269800,290178,311556
%N A262402 a(n) = number of triangles that can be formed from the points of a 3 X n grid.
%H A262402 Andrew Howroyd, <a href="/A262402/b262402.txt">Table of n, a(n) for n = 1..1000</a>
%H A262402 Jared Nash, <a href="/A262402/a262402.pdf">Formula for number of triangles in a 3 X n grid</a>
%H A262402 Ran Pan, <a href="http://www.math.ucsd.edu/~projectp/warmups/eT.html">Exercise T</a>, Project P, 2015.
%H A262402 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (3,-2,-2,3,-1).
%F A262402 a(n) = n^2*(8*n-7)/2 - (n mod 2)/2. - _Jared Nash_, Dec 14 2017
%F A262402 Proof of Jared Nash's formula, from _N. J. A. Sloane_, Dec 16 2017 (Start).
%F A262402 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).
%F A262402 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).
%F A262402 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)
%F A262402 For another proof, see the link.
%F A262402 G.f.: 2*x^2*(4*x^2 + 11*x + 9) / ((1 - x)^3*(1 - x^2)). - _N. J. A. Sloane_, Dec 16 2017
%F A262402 From _Colin Barker_, Dec 20 2017: (Start)
%F A262402 a(n) = n^2*(8*n - 7) / 2 for n even.
%F A262402 a(n) = (8*n^3 - 7*n^2 - 1) / 2 for n odd.
%F A262402 a(n) = 3*a(n-1) - 2*a(n-2) - 2*a(n-3) + 3*a(n-4) - a(n-5) for n>5.
%F A262402 (End)
%p A262402 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
%t A262402 LinearRecurrence[{3, -2, -2, 3, -1}, {0, 18, 76, 200, 412}, 50] (* _Jean-François Alcover_, Aug 26 2019 *)
%o A262402 (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
%Y A262402 Cf. A115514, A045996, A296367.
%Y A262402 The old, incorrect, formula proposed for this problem is now in A296363.
%K A262402 nonn,easy
%O A262402 1,2
%A A262402 _Ran Pan_, Sep 21 2015
%E A262402 Terms corrected and entry revised by _N. J. A. Sloane_, Dec 16 2017 following an email from _Jared Nash_, Dec 14 2017.