|
%I #37 Jun 13 2020 16:13:14
%S 0,48,200,516,1056,1884,3052,4628,6668,9232,12380,16176,20672,25936,
%T 32024,38996,46912,55836,65820,76932,89228,102768,117612,133824,
%U 151456,170576,191240,213508,237440,263100,290540,319828,351020,384176,419356,456624,496032,537648,581528,627732,676320
%N Number of triangles on a 4 X n grid.
%H Colin Barker, <a href="/A296367/b296367.txt">Table of n, a(n) for n = 1..1000</a>
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,-1,0,2,-1).
%F a(n) = 2*n*(n-1)*(5*n+2) - 4*floor((n-1)^2/4) - 4*floor((n-1)*(n-2)/6).
%F Proof: We will show that a(n) = 6*n^2*(n-1) + 2*(n^3 - n - 2*floor((n-1)^2/4)) + 2*(n^3 - n - 2*floor((n-1)*(n-2)/6)), which is equivalent to the above formula. The argument is similar to that used to prove the formula for A262402.
%F There are three cases. On a 4Xn grid of points, a triangle can either have (I) 2 points on one line and 1 point on another line, (II) one point on each of lines 1,2,3 or 2,3,4, or (III) one point on each of lines 1,2,4 or 1,3,4.
%F (I) The triangle can be drawn in 4*3*binomial(n,2)*n = 6*n^2*(n-1) ways.
%F (II) Suppose the points are on lines 1,2,3. The number of triangles is n^3 - Q, where Q is the number of degenerate triangles formed by collinear triples with one point on each of lines 1,2,3. 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, d >= 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 in the "1,2,3" case the number of triangles is n^3 - n - 2*floor((n-1)^2/4). The same number arises in the "2,3,4" case.
%F (III) Suppose the points are on lines 1,2,4. The number of triangles is n^3 - Q, where Q is the number of degenerate triangles formed by collinear triples with one point on each of lines 1,2,4. There are n vertical triples. If the three points are on a downward sloping line, through points (1,i), (2,i+d, i+3d), say, with i >= 1, d >= 1, i+3d <= n, there are Sum_{i=1..n-2} floor((n-i)/2) possibilities, and this sum is equal to floor((n-1)*(n-2)/6) (see A001840). So in this case there are n^3 - n - 2*floor((n-1)*(n-2)/6) triangles. The same number arises in the "1,3,4" case. QED.
%F G.f.: 4*x^2*(5*x^4+18*x^3+29*x^2+26*x+12)/((1-x)^2*(1-x^2)*(1-x^3)).
%F a(n) = 2*a(n-1) - a(n-3) - a(n-4) + 2*a(n-6) - a(n-7) for n>7. - _Colin Barker_, Dec 26 2017
%p A:=proc(n)
%p 6*n^2*(n-1)
%p + 2*(n^3 - n - 2*floor((n-1)^2/4))
%p + 2*(n^3 - n - 2*floor((n-1)*(n-2)/6));
%p end;
%p [seq(A(n),n=1..64)];
%o (PARI) concat(0, Vec(4*x^2*(12 + 26*x + 29*x^2 + 18*x^3 + 5*x^4) / ((1 - x)^4*(1 + x)*(1 + x + x^2)) + O(x^40))) \\ _Colin Barker_, Dec 26 2017
%Y Cf. A001840, A045996, A115514, A262402.
%K nonn,easy
%O 1,2
%A _Jared Nash_ and _N. J. A. Sloane_, Dec 19 2017, corrected Dec 23 2017
|
