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,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). - 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

Cf. A094777.

Cf. A030236, A098182.

Sequence in context: A337207 A080870 A288414 * A211380 A053731 A111295

Adjacent sequences: A102617 A102618 A102619 * A102621 A102622 A102623

Keyword

nonn

Author

John Tromp, Jan 31 2005

Extensions

More terms from Joerg Arndt, Apr 17 2013

Status

approved