A102620 -id:A102620 - cp's OEIS frontend

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

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

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.

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

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

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

Extensions

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

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

Examples

Links

Crossrefs

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

Views

Author

Keywords

Comments

Crossrefs