A102620 Number of legal Go positions on a 1 X n board (for which 3^n is a trivial upper bound).
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
Offset: 1
Keywords
Examples
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.
Links
- John Tromp, The Logical Rules of Go
- Index entries for linear recurrences with constant coefficients, signature (3,-1,1).
Programs
-
Mathematica
LinearRecurrence[{3,-1,1},{1,5,15},40] (* Harvey P. Dale, Sep 16 2016 *) -
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
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
Extensions
More terms from Joerg Arndt, Apr 17 2013