login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A094777 Number of legal positions in Go played on an n X n grid (each group must have at least one liberty). 7
1, 57, 12675, 24318165, 414295148741, 62567386502084877, 83677847847984287628595, 990966953618170260281935463385, 103919148791293834318983090438798793469, 96498428501909654589630887978835098088148177857, 793474866816582266820936671790189132321673383112185151899, 57774258489513238998237970307483999327287210756991189655942651331169, 37249792307686396442294904767024517674249157948208717533254799550970595875237705, 212667732900366224249789357650440598098805861083269127196623872213228196352455447575029701325 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

LINKS

John Tromp, Table of n, a(n) for n = 1..19

British Go Association, Go

Sandy Harris, Number of Possible Outcomes of a Game

John Tromp, Complexity of Chess and Go

John Tromp, Number of legal Go positions

John Tromp and Gunnar Farneb├Ąck, Combinatorics of Go (2016)

FORMULA

3^(n*n) is a trivial upper bound.

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

EXAMPLE

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.

CROSSREFS

Sequence in context: A219077 A091749 A218425 * A218662 A093257 A210148

Adjacent sequences:  A094774 A094775 A094776 * A094778 A094779 A094780

KEYWORD

nonn

AUTHOR

Jan Kristian Haugland (jankrihau(AT)hotmail.com), Jun 09 2004

EXTENSIONS

More terms from John Tromp, Jan 27 2005

a(10)-a(13) from John Tromp, Jun 23 2005

a(14)-a(15) from John Tromp, Sep 01 2005.

a(16) from John Tromp, Oct 06 2005

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.

a(17)-a(18) from John Tromp, Mar 08 2015

a(19) from John Tromp, Jan 21 2016

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 25 18:20 EDT 2017. Contains 292499 sequences.