|
|
A355551
|
|
Number of ways to select 3 or more collinear points from a 3 X n grid.
|
|
2
|
|
|
1, 2, 8, 23, 61, 144, 322, 689, 1439, 2954, 6004, 12123, 24385, 48932, 98054, 196325, 392899, 786078, 1572472, 3145295, 6290981, 12582392, 25165258, 50331033, 100662631, 201325874, 402652412, 805305539, 1610611849, 3221224524, 6442449934
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 3*(2^n - 1 - n*(n+1)/2) + ceiling(n^2/2).
a(n) ~ 3*2^n.
G.f.: x*(1 - 2*x + 4*x^2 + x^3)/((1 - x)^3*(1 - x - 2*x^2)).
a(n) = (3*2^(n+2) - 4*n^2 - 6*n - 11 - (-1)^n)/4. (End)
|
|
EXAMPLE
|
a(5)=61: there are 3*(2^5 - 1 - binomial(6,2)) ways to select 3 or more points on a horizontal line, 5 ways on a vertical line, 3 ways on a diagonal line with slope 1, 3 ways on a diagonal line with slope -1, 1 way on a diagonal line with slope 1/2, and 1 way on a diagonal line with slope -1/2; 48 + 5 + 6 + 2 = 61.
|
|
PROG
|
(Python)
def a(n): return 3*((1<<n) - 1 - n*(n+1)//2)+(n**2+1)//2
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|