cp's OEIS Frontend

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

%I A327821 #22 Oct 06 2020 02:43:46
%S A327821 1,5,19,57,161,449,1247,3457,9577,26525,73459,203433,563369,1560137,
%T A327821 4320479,11964673
%N A327821 Number of legal Go positions on a board which is an n-cycle graph.
%C A327821 This is a variation on A102620.
%H A327821 Sébastien Palcoux, <a href="https://mathoverflow.net/q/342194/34538">Is this representation of Go (game) irreducible?</a> (version: 2019-09-22), MathOverflow.
%F A327821 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.
%F A327821 From _Colin Barker_, Sep 26 2019: (Start)
%F A327821 G.f.: x*(1 + x + 3*x^2 - x^3) / ((1 - x)*(1 - 3*x + x^2 - x^3)).
%F A327821 a(n) = 4*a(n-1) - 4*a(n-2) + 2*a(n-3) - a(n-4) for n > 4.
%F A327821 (End)
%F A327821 From _Zhujun Zhang_, Sep 28 2020: (Start)
%F A327821 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.
%F A327821 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.
%F A327821 (End)
%e A327821 A 2-cycle is a 1 X 2 grid so that a(2) = A102620(2) = A266278(1) = 5.
%e A327821 A 4-cycle is a 2 X 2 grid so that a(4) = A094777(2) = A266278(2) = 57.
%o A327821 (SageMath)
%o A327821 cpdef GoCycle(int n):
%o A327821    cdef int i,j,a,l
%o A327821    cdef list L,LL,T
%o A327821    LL=[]
%o A327821    for i in range(3**n):
%o A327821       L=Integer(i).digits(base=3,padto=n)
%o A327821       T=[L[0]]
%o A327821       for j in range(n-1):
%o A327821          if L[j+1]<>L[j]:
%o A327821             T.append(L[j+1])
%o A327821       if len(T)>1 and T[0]==T[-1]:
%o A327821          T.pop(0)
%o A327821       a=1
%o A327821       if 1 in T:
%o A327821          a=0
%o A327821          l=len(T)
%o A327821          if l>2:
%o A327821             for j in range(-2,l-2):
%o A327821                if not 1 in [T[j],T[j+1],T[j+2]]:
%o A327821                   a=1
%o A327821                   break
%o A327821       if a==0:
%o A327821          L=[j-1 for j in L]
%o A327821          LL.append(L)
%o A327821    return LL
%o A327821 [len(GoCycle(i)) for i in range(1,17)]
%Y A327821 Cf. A094777, A102620, A266278, A268113.
%K A327821 nonn,more
%O A327821 1,2
%A A327821 _Sébastien Palcoux_, Sep 26 2019