login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102620 Number of legal Go positions on a 1 X n board (for which 3^n is a trivial upper bound). 6

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 28 09:04 EDT 2024. Contains 371240 sequences. (Running on oeis4.)