login
This site is supported by donations 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). 2
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

Table of n, a(n) for n=1..35.

John Tromp, The Logical Rules of Go

Index entries for linear recurrences with constant coefficients, signature (3,-1,1).

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) [From Josh Simmons (jsimmons10(AT)my.whitworth.edu), May 06 2010]

a(n)=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) [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

Cf. A094777.

Cf. A030236, A098182.

Sequence in context: A113861 A080870 A288414 * A211380 A053731 A111295

Adjacent sequences:  A102617 A102618 A102619 * A102621 A102622 A102623

KEYWORD

nonn

AUTHOR

John Tromp, Jan 31 2005

EXTENSIONS

More terms, Joerg Arndt, Apr 17 2013

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 23 16:14 EDT 2019. Contains 325258 sequences. (Running on oeis4.)