cp's OEIS Frontend

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

%I A094777 #58 Mar 24 2025 19:39:36
%S A094777 1,57,12675,24318165,414295148741,62567386502084877,
%T A094777 83677847847984287628595,990966953618170260281935463385,
%U A094777 103919148791293834318983090438798793469,96498428501909654589630887978835098088148177857,793474866816582266820936671790189132321673383112185151899,57774258489513238998237970307483999327287210756991189655942651331169,37249792307686396442294904767024517674249157948208717533254799550970595875237705,212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325
%N A094777 Number of legal positions in Go played on an n X n grid (each group must have at least one liberty).
%C A094777 John Tromp wrote a small C program to compute the number for boards up to size 4 X 5, given in the rec.games.go posting below. Gunnar Farnebaeck (gunnar(AT)lysator.liu.se) wrote a pike script to compute the number by dynamic programming, which handles sizes up to 12 X 12 (available upon request).
%H A094777 John Tromp, <a href="/A094777/b094777.txt">Table of n, a(n) for n = 1..19</a>
%H A094777 British Go Association, <a href="http://www.britgo.org/">Go</a>
%H A094777 Sandy Harris, <a href="http://senseis.xmp.net/?NumberOfPossibleOutcomesOfAGame">Number of Possible Outcomes of a Game</a>
%H A094777 John Tromp, <a href="http://groups-beta.google.com/group/rec.games.go/browse_frm/thread/787f07f3541004ed/26fd571996bbbf49">Complexity of Chess and Go</a>
%H A094777 John Tromp, <a href="http://tromp.github.io/go/legal.html">Number of legal Go positions</a>
%H A094777 John Tromp and Gunnar Farnebäck, <a href="https://tromp.github.io/go/gostate.pdf">Combinatorics of Go</a> (2016)
%H A094777 Zach Weinersmith, <a href="http://www.smbc-comics.com/comic/branch">A New Branch of Mathematics</a>, SMBC (Saturday Morning Breakfast Cereal) column, Mar 24 2025 [Mentions this sequence] (Link provided by _Jeffrey Shallit_, Mar 24 2025)
%F A094777 3^(n*n) is a trivial upper bound.
%F A094777 Tromp & Farnebäck prove that a(n) = (1 + o(1)) * L^(n^2), and conjecture that a(n) ~ A * B^(2n) * L^(n^2) * (1 + O(n*p^n)) for some constants A, B, L, and p < 1. - _Charles R Greathouse IV_, Feb 08 2016
%e A094777 The illegal 2 X 2 positions are the 2^4 with no empty points and the 4*2 having a stone adjacent to 2 opponent stones that share a liberty. That leaves 3^4-16-8 = 57 legal positions.
%K A094777 nonn
%O A094777 1,2
%A A094777 _Jan Kristian Haugland_, Jun 09 2004
%E A094777 More terms from _John Tromp_, Jan 27 2005
%E A094777 a(10)-a(13) from _John Tromp_, Jun 23 2005
%E A094777 a(14)-a(15) from _John Tromp_, Sep 01 2005
%E A094777 a(16) from _John Tromp_, Oct 06 2005
%E A094777 Michal Koucky should be credited for carrying most of the computational load for computing the n=14, 15 and 16 results with his file-based implementation.
%E A094777 a(17)-a(18) from _John Tromp_, Mar 08 2015
%E A094777 a(19) from _John Tromp_, Jan 21 2016