A100583 Number of triangles in an n X n grid of squares with diagonals.
0, 8, 44, 124, 268, 492, 816, 1256, 1832, 2560, 3460, 4548, 5844, 7364, 9128, 11152, 13456, 16056, 18972, 22220, 25820, 29788, 34144, 38904, 44088, 49712, 55796, 62356, 69412, 76980, 85080, 93728, 102944, 112744, 123148, 134172, 145836
Offset: 0
Links
- Author?, WisFaq (Dutch)
- Dave Richeson, Counting triangles on a tin ceiling (solution, take 2) (2011)
- Index entries for linear recurrences with constant coefficients, signature (3,-2,-2,3,-1).
Programs
-
PARI
a(n)=3*n^3+9*n^2\2+n \\ Charles R Greathouse IV, Aug 19 2014
Formula
a(n) = (12*n^3+18*n^2+4*n+(-1)^n-1)/4. (For a proof see the Richeson link.)
a(n) = 4*Sum{i=1 to n}(i^2 + (n+1-i)*(n+1-round(i/2))).
G.f.: 4*x*(x+2)*(2*x+1) / ((x-1)^4*(x+1)). - Colin Barker, Aug 19 2014