A094777 -id:A094777 - cp's OEIS frontend

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

John Tromp, Jan 31 2005

nonn

			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.

John Tromp, The Logical Rules of Go
Index entries for linear recurrences with constant coefficients, signature (3,-1,1).

Cf. A094777.

Cf. A030236, A098182.

LinearRecurrence[{3,-1,1},{1,5,15},40] (* Harvey P. Dale, Sep 16 2016 *)

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 */

Vec(x*(1+x)^2/((1-x)^3-2*x^2)+O(x^66)) \\ Joerg Arndt, Apr 17 2013

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

More terms from Joerg Arndt, Apr 17 2013

A266278 Number of legal Go positions on a 2 X n board.

Original entry on oeis.org

5, 57, 489, 4125, 35117, 299681, 2557605, 21826045, 186255781, 1589441093, 13563736693, 115748216413, 987755062201, 8429158472781, 71931509371765, 613838505628281, 5238284505542721, 44701699729693429, 381468772192258129, 3255321946095461785, 27779786302899765081

Offset: 1

Felix Fröhlich, Dec 26 2015

			For n = 1, the a(1) = 5 legal 2 X 1 boards are .. X. O. .X .O

Colin Barker, Table of n, a(n) for n = 1..1000
John Tromp, Number of legal 2xn Go positions
J. Tromp and G. Farnebäck, Combinatorics of Go, Lecture Notes in Computer Science, 4630, 84-99, 2007.
Index entries for linear recurrences with constant coefficients, signature (10,-16,31,-13,20,2,-1).

Cf. A094777, A102620.

Vec(x*(1 + x)^2*(5 - 3*x - 5*x^3 - x^4) / ((1 + x^2)*(1 - 10*x + 15*x^2 - 21*x^3 - 2*x^4 + x^5)) + O(x^40)) \\ Colin Barker, Jan 05 2018

a(n) = 10*a(n-1)-16*a(n-2)+31*a(n-3)-13*a(n-4)+20*a(n-5)+2*a(n-6)-a(n-7).

G.f.: x*(1 + x)^2*(5 - 3*x - 5*x^3 - x^4) / ((1 + x^2)*(1 - 10*x + 15*x^2 - 21*x^3 - 2*x^4 + x^5)). - Colin Barker, Jan 05 2018

Corrected and edited by John Tromp, Jan 26 2016

A268113 Number of legal positions in Go played on an n X n+1 grid (each group must have at least one liberty).

Original entry on oeis.org

5, 489, 321689, 1840058693, 93332304864173, 41945191530093646965, 166931297609667912727898521, 5882748866432370655674372752123193, 1835738613899845421140262364853644706891109, 5072588588647327658457862518216696854885169490987149

Offset: 1

John Tromp, Jan 26 2016

Upper bounded by 3^{n*(n+1)}.

			For n=1 the 5 legal 1x2 boards are .. X. O. .X .O

John Tromp, Table of n, a(n) for n = 1..19
John Tromp, Number of legal Go positions
J. Tromp and G. Farnebäck, Combinatorics of Go, Lecture Notes in Computer Science, 4630, 84-99, 2007.

Almost-square version of A094777.

A356049 Symmetric array read by antidiagonals: T(n,k) is the number of legal positions in Go on an n X k board.

Original entry on oeis.org

1, 5, 5, 15, 57, 15, 41, 489, 489, 41, 113, 4125, 12675, 4125, 113, 313, 35117, 321689, 321689, 35117, 313, 867, 299681, 8180343, 24318165, 8180343, 299681, 867, 2401, 2557605, 208144601, 1840058693, 1840058693, 208144601, 2557605, 2401

Offset: 1

Douglas Boffey, Jul 24 2022

A Go position is a grid containing white and black stones with the condition that every orthogonally connected group of stones of a single color has liberties, i.e., is orthogonally adjacent to an empty cell.

			Array begins:
   1,   5,  15,  41, ...
   5,  57, 489, ...
  15, 489, ...
  41, ...
  ...
T(3,1) = 15 from
  ... ..w ..b .w. .ww  .b. .bb w.. w.w w.b  ww. b.. b.w b.b bb.

Douglas Boffey, Table of n, a(n) for n = 1..528
J. Tromp, Number of Legal Go Positions

Columns (or rows) give: A102620, A266278.
Main diagonal gives A094777.
This as triangle gives A356134.

A356134 Triangular array giving total number of legal Go positions on an n X k board.

Original entry on oeis.org

1, 5, 57, 15, 489, 12675, 41, 4125, 321689, 24318165, 113, 35117, 8180343, 1840058693, 414295148741, 313, 299681, 208144601, 139304759213, 93332304864173, 62567386502084877, 867, 2557605, 5296282323, 10546705714473, 21026744638200555, 41945191530093646965, 83677847847984287628595

Offset: 1

Douglas Boffey, Jul 27 2022

			Triangle T(n,k) begins:
    1;
    5,    57;
   15,   489,   12675;
   41,  4125,  321689,   24318165;
  113, 35117, 8180343, 1840058693, 414295148741;
  ...

Douglas Boffey, Table of n, a(n) for n = 1..190 (rows 1..19 flattened).
J. Tromp, Number of Legal Go Positions

Columns give: A102620, A266278.
Main diagonal gives A094777.
A356049 gives the table by antidiagonals.

a(27) corrected by Sidney Cadot, Jan 05 2023.

A269417 Number of Go games on n X n board with no repeating position and suicide allowed.

Original entry on oeis.org

1, 1, 386356909593

Offset: 0

John Tromp, Feb 25 2016

I only chose starting offset 0 because the number of 3 X 3 games is unknown (and over a thousand digits).
a(n) is also the number of simple paths in the Go game graph starting at the empty position.
a(n) is upper bounded by n^{2*3^{n^2}}, as shown in Theorem 7 from the linked paper.

			a(1) = 1 since the only legal Go game on a 1 X 1 board is Black pass, White pass.

J. Tromp and G. Farnebäck, Combinatorics of Go, Lecture Notes in Computer Science, 4630, 84-99, 2007.

Cf. A094777.

A275346 In Go, minimum total number of liberties player 1 (black) can have on a standard 19 X 19 board after n moves when no player passes a move, with no repeating game positions allowed.

Original entry on oeis.org

2, 1, 2, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1

Offset: 1

Felix Fröhlich, Jul 24 2016

nonn

For many small n, a(n) = 0 when n is even and a(n) = 1 when n is odd, because a row of black stones can be played on the outer line of the board with a row of white stones running adjacent to the black stones, as in the following diagram:
B--B--W
|
B--W
|
B--W
|
B--W
|
o
What is the asymptotic behavior of this sequence?
Does a(n) exist for all n or does a constant c exist such that a(n) is undefined for n >= c (because no more legal moves are possible)?

			n=1: B--o
     |
     o
n=2: B--o  B--W
     |     |
     o     o
n=3: B--o  B--W  B--W
     |     |     |
     o     o     B--o
                 |
                 o
n=4: B--o  B--W  B--W  B--W
     |     |     |     |
     o     o     B--o  B--W
                 |     |
                 o     o
n=5: o     o     B--o  B--o  B--B--o
     |     |     |     |     |  |
     B--o  B--o  B--o  B--W  B--W
     |     |     |     |     |
     o     W     W     W     W
n=6: o     o     o--B--o  o--B--o  B--B--o  .--.--W
     |     |     |  |     |  |     |  |     |  |
     B--o  B--o  B--o     B--W     B--W     .--W
     |     |     |        |        |        |
     o     W     W        W        W        W

online-go.com, Learn to play Go: Placing stones (virtual 9x9 Go board).
Wikipedia, Go (game).

Cf. A089071, A094777, A269417.

A327821 Number of legal Go positions on a board which is an n-cycle graph.

Original entry on oeis.org

1, 5, 19, 57, 161, 449, 1247, 3457, 9577, 26525, 73459, 203433, 563369, 1560137, 4320479, 11964673

Offset: 1

Sébastien Palcoux, Sep 26 2019

This is a variation on A102620.

			A 2-cycle is a 1 X 2 grid so that a(2) = A102620(2) = A266278(1) = 5.
A 4-cycle is a 2 X 2 grid so that a(4) = A094777(2) = A266278(2) = 57.

Sébastien Palcoux, Is this representation of Go (game) irreducible? (version: 2019-09-22), MathOverflow.

Cf. A094777, A102620, A266278, A268113.

cpdef GoCycle(int n):
   cdef int i,j,a,l
   cdef list L,LL,T
   LL=[]
   for i in range(3**n):
      L=Integer(i).digits(base=3,padto=n)
      T=[L[0]]
      for j in range(n-1):
         if L[j+1]<>L[j]:
            T.append(L[j+1])
      if len(T)>1 and T[0]==T[-1]:
         T.pop(0)
      a=1
      if 1 in T:
         a=0
         l=len(T)
         if l>2:
            for j in range(-2,l-2):
               if not 1 in [T[j],T[j+1],T[j+2]]:
                  a=1
                  break
      if a==0:
         L=[j-1 for j in L]
         LL.append(L)
   return LL
[len(GoCycle(i)) for i in range(1,17)]

a(n)/A102620(n) converges to 1.44066.... This would imply that a(n+1)/a(n) converges to 2.769292354... the real root of x^3 - 3*x^2 + x - 1 = 0.
From Colin Barker, Sep 26 2019: (Start)
G.f.: x*(1 + x + 3*x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2 - x^3)).
a(n) = 4*a(n-1) - 4*a(n-2) + 2*a(n-3) - a(n-4) for n > 4.
(End)
From Zhujun Zhang, Sep 28 2020: (Start)
a(n) = r_1^n + r_2^n + r_3^n - 2 where r_1, r_2 and r_3 are roots of x^3 - 3*x^2 + x - 1 = 0 for n > 0.
a(n) = floor(r^n - 3/2) where r is the real root of x^3 - 3*x^2 + x - 1 = 0 for n > 2.
(End)

A268125 Minimal order of recurrence for number of legal n X m Go positions, for fixed n.

Original entry on oeis.org

3, 7, 19, 57, 217, 791, 3107, 12110, 49361

Offset: 1

John Tromp, Jan 26 2016

			For n=1 the minimal recurrence is L(1,m) = 3*L(1,m-1)-L(1,m-2)+L(1,m-3).

J. Tromp and G. Farnebäck, Combinatorics of Go, Lecture Notes in Computer Science, 4630, 84-99, 2007.

Cf. A094777, A102620, A266278.

A337207 a(n) is the minimal number of legal positions in Go played on connected graphs with n nodes.

Original entry on oeis.org

1, 5, 15, 41, 107, 273, 707, 1817, 4617, 11867, 30425, 76857, 197603, 505871, 1275465, 3276563, 8406527, 21165273, 54338627, 139513379, 351447657, 901789811, 2304725075, 5840498937, 14978318243, 38107010435, 97141424265, 248995117523, 630641012147

Offset: 1

Zhujun Zhang, Aug 19 2020

nonn

Consider a Go game played on general graphs instead of grids. The position that each group has at least one liberty is called a legal position. 2^(n+1)-3 and 3^n-2^n are respectively the trivial lower bound and upper bound of this sequence. The Mathematics of Go interest group computed this sequence up to n=481.

Cf. A094777, A102620, A266278, A268113, A327821.

cp's OEIS Frontend

A102620 Number of legal Go positions on a 1 X n board (for which 3^n is a trivial upper bound).

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

Maxima

PARI

Formula

Extensions

A266278 Number of legal Go positions on a 2 X n board.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

A268113 Number of legal positions in Go played on an n X n+1 grid (each group must have at least one liberty).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A356049 Symmetric array read by antidiagonals: T(n,k) is the number of legal positions in Go on an n X k board.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A356134 Triangular array giving total number of legal Go positions on an n X k board.

Views

Author

Keywords

Examples

Links

Crossrefs

Extensions

A269417 Number of Go games on n X n board with no repeating position and suicide allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A275346 In Go, minimum total number of liberties player 1 (black) can have on a standard 19 X 19 board after n moves when no player passes a move, with no repeating game positions allowed.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A327821 Number of legal Go positions on a board which is an n-cycle graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

SageMath

Formula

A268125 Minimal order of recurrence for number of legal n X m Go positions, for fixed n.

Views

Author

Keywords