%I #29 Jun 25 2021 01:39:26
%S 1,5,15,41,113,313,867,2401,6649,18413,50991,141209,391049,1082929,
%T 2998947,8304961,22998865,63690581,176377839,488441801,1352638145,
%U 3745850473,10373355075,28726852897,79553054089,220305664445,610090792143,1689519766073,4678774170521,12956893537633,35881426208451,99366159258241,275173945103905,762037102261925,2110303520940111
%N Number of legal Go positions on a 1 X n board (for which 3^n is a trivial upper bound).
%H John Tromp, <a href="https://tromp.github.io/go.html">The Logical Rules of Go</a>
%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (3,-1,1).
%F For n >= 4, a(n) = 3*a(n-1) - a(n-2) + a(n-3).
%F G.f.: x(1+x)^2/((1-x)^3-2x^2). - Josh Simmons (jsimmons10(AT)my.whitworth.edu), May 06 2010
%F 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
%e 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.
%t LinearRecurrence[{3,-1,1},{1,5,15},40] (* _Harvey P. Dale_, Sep 16 2016 *)
%o (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 */
%o (PARI) Vec(x*(1+x)^2/((1-x)^3-2*x^2)+O(x^66)) \\ _Joerg Arndt_, Apr 17 2013
%Y Cf. A094777.
%Y Cf. A030236, A098182.
%K nonn
%O 1,2
%A _John Tromp_, Jan 31 2005
%E More terms from _Joerg Arndt_, Apr 17 2013