cp's OEIS Frontend

A320666 a(n) is the maximum number of liberties a single group can have on an otherwise empty n X n Go board.

%I A320666 #43 Mar 26 2021 04:43:18
%S A320666 0,2,6,9,14,22,29,38,51,61,74,92,105,122,145,161,182,210,229,254,287,
%T A320666 309,338,376
%N A320666 a(n) is the maximum number of liberties a single group can have on an otherwise empty n X n Go board.
%C A320666 For 1 X 1 the solution is a single stone on the only possible position and is not a valid final board state in a real game of Go.
%C A320666 Also seems to be the answer to the following parking problem: maximum number of cars in an n X n carpark such that any car can leave through a single exit. See Puzzling StackExchange links. - _Dmitry Kamenetsky_, Mar 26 2021
%H A320666 Ton Hospel, <a href="https://github.com/thospel/Go-CountLiberties">Table of n, a(n) for n = 1..24</a>
%H A320666 Puzzling StackExchange, <a href="https://puzzling.stackexchange.com/questions/107886/placing-9-cars-into-a-4x4-carpark">Placing 9 cars into a 4x4 carpark</a>, March 2021.
%H A320666 Puzzling StackExchange, <a href="https://puzzling.stackexchange.com/questions/55853/a-special-parking-lot">A special parking lot</a>, October 2017.
%F A320666 Exact for n <= 24, conjectured for n > 24 but it is at least a lower bound:
%F A320666   a(n) = 0 if n = 1.
%F A320666   a(n) = 2 if n = 2.
%F A320666   a(n) = 6 if n = 3.
%F A320666   a(n) = n*(2*n-1)/3    if n = 0 (mod 3) and n != 3.
%F A320666   a(n) = ((2n-1)^2+5)/6 if n = 1 (mod 3) and n != 1.
%F A320666   a(n) = ((2n-1)^2+3)/6 if n = 2 (mod 3).
%F A320666 Conjectures from _Colin Barker_, Jun 05 2019: (Start)
%F A320666 G.f.: x^2*(2 + 4*x + 3*x^2 + x^3 + x^5 + x^6 + x^7 - x^8) / ((1 - x)^3*(1 + x + x^2)^2).
%F A320666 a(n) = a(n-1) + 2*a(n-3) - 2*a(n-4) - a(n-6) + a(n-7) for n>9.
%F A320666 (End)
%e A320666 For n = 7 one of many a(7) = 29 solutions:
%e A320666   *********
%e A320666   *.O.....*
%e A320666   *.OOOOOO*
%e A320666   *.O....O*
%e A320666   *.O.....*
%e A320666   *.O.OOO.*
%e A320666   *.OOO.O.*
%e A320666   *.O...O.*
%e A320666   *********
%o A320666 (Perl)
%o A320666 sub a {
%o A320666      # Conjectured: This program is valid for any m X n board size
%o A320666      my ($m, $n) = @_;
%o A320666      $n = $m if !defined $n;
%o A320666      ($m, $n) = ($n, $m) if $m > $n;
%o A320666      # So now $m <= $n
%o A320666      # This program is certain to be valid for all $m <= 24
%o A320666      if ($m >= 4) {
%o A320666          return $m*(2*$n-1)/3 if $m % 3 == 0;
%o A320666          return $n*(2*$m-1)/3 if $n % 3 == 0;
%o A320666          return ((2*$m-1)*(2*$n-1)+5)/6 if $m % 3 == 1 && $n % 3 == 1;
%o A320666          return ((2*$m-1)*(2*$n-1)+3)/6; # if $m % 3 == 2 || $n % 3 == 2
%o A320666      }
%o A320666      return 2*$n if $m == 3;
%o A320666      return $n == 3 ? 4 : $n if $m == 2;
%o A320666      return $n >= 3 ? 2 : $n-1 if $m == 1;
%o A320666      die "Bad call";
%o A320666 }
%Y A320666 A071619 is a trivial upper bound for this sequence.
%K A320666 nonn,more
%O A320666 1,2
%A A320666 _Ton Hospel_, Oct 28 2018