login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A296367 Number of triangles on a 4 X n grid. 1
0, 48, 200, 516, 1056, 1884, 3052, 4628, 6668, 9232, 12380, 16176, 20672, 25936, 32024, 38996, 46912, 55836, 65820, 76932, 89228, 102768, 117612, 133824, 151456, 170576, 191240, 213508, 237440, 263100, 290540, 319828, 351020, 384176, 419356, 456624, 496032, 537648, 581528, 627732, 676320 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

LINKS

Colin Barker, Table of n, a(n) for n = 1..1000

Index entries for linear recurrences with constant coefficients, signature (2,0,-1,-1,0,2,-1).

FORMULA

a(n) = 2*n*(n-1)*(5*n+2) - 4*floor((n-1)^2/4) - 4*floor((n-1)*(n-2)/6).

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.

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.

(I) The triangle can be drawn in 4*3*binomial(n,2)*n = 6*n^2*(n-1) ways.

(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.

(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.

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)).

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

MAPLE

A:=proc(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));

end;

[seq(A(n), n=1..64)];

PROG

(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

CROSSREFS

Cf. A001840, A115514, A262402.

Sequence in context: A231174 A259245 A157923 * A275507 A072254 A290350

Adjacent sequences:  A296364 A296365 A296366 * A296368 A296369 A296370

KEYWORD

nonn,easy

AUTHOR

Jared Nash and N. J. A. Sloane, Dec 19 2017, corrected Dec 23 2017

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 4 05:34 EDT 2020. Contains 333212 sequences. (Running on oeis4.)