|
|
A102620
|
|
Number of legal Go positions on a 1 X n board (for which 3^n is a trivial upper bound).
|
|
6
|
|
|
1, 5, 15, 41, 113, 313, 867, 2401, 6649, 18413, 50991, 141209, 391049, 1082929, 2998947, 8304961, 22998865, 63690581, 176377839, 488441801, 1352638145, 3745850473, 10373355075, 28726852897, 79553054089, 220305664445, 610090792143, 1689519766073, 4678774170521, 12956893537633, 35881426208451, 99366159258241, 275173945103905, 762037102261925, 2110303520940111
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
FORMULA
|
For n >= 4, a(n) = 3*a(n-1) - a(n-2) + a(n-3).
G.f.: x(1+x)^2/((1-x)^3-2x^2). - Josh Simmons (jsimmons10(AT)my.whitworth.edu), May 06 2010
a(n) = Sum_{k=0..floor((n-1)/2)} 2^k * (binomial(n+k+1,3*k+2) + 2*binomial(n+k,3*k+2) + binomial(n+k-1,3*k+2)). - Emanuele Munarini, Apr 17 2013
|
|
EXAMPLE
|
a(2)=5 because .. .O .S O. S. are the 5 legal 1 X 2 Go positions, while OO OS SO SS are all illegal, having stones without liberties.
|
|
MATHEMATICA
|
LinearRecurrence[{3, -1, 1}, {1, 5, 15}, 40] (* Harvey P. Dale, Sep 16 2016 *)
|
|
PROG
|
(Maxima) makelist(sum((2^k)*(binomial(n+k+1, 3*k+2)+2*binomial(n+k, 3*k+2)+binomial(n+k-1, 3*k+2)), k, 0, (n-1)/2), n, 0, 24); /* Emanuele Munarini, Apr 17 2013 */
(PARI) Vec(x*(1+x)^2/((1-x)^3-2*x^2)+O(x^66)) \\ Joerg Arndt, Apr 17 2013
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|