A320666 a(n) is the maximum number of liberties a single group can have on an otherwise empty n X n Go board.
0, 2, 6, 9, 14, 22, 29, 38, 51, 61, 74, 92, 105, 122, 145, 161, 182, 210, 229, 254, 287, 309, 338, 376
Offset: 1
Examples
For n = 7 one of many a(7) = 29 solutions: ********* *.O.....* *.OOOOOO* *.O....O* *.O.....* *.O.OOO.* *.OOO.O.* *.O...O.* *********
Links
- Ton Hospel, Table of n, a(n) for n = 1..24
- Puzzling StackExchange, Placing 9 cars into a 4x4 carpark, March 2021.
- Puzzling StackExchange, A special parking lot, October 2017.
Crossrefs
A071619 is a trivial upper bound for this sequence.
Programs
-
Perl
sub a { # Conjectured: This program is valid for any m X n board size my ($m, $n) = @_; $n = $m if !defined $n; ($m, $n) = ($n, $m) if $m > $n; # So now $m <= $n # This program is certain to be valid for all $m <= 24 if ($m >= 4) { return $m*(2*$n-1)/3 if $m % 3 == 0; return $n*(2*$m-1)/3 if $n % 3 == 0; return ((2*$m-1)*(2*$n-1)+5)/6 if $m % 3 == 1 && $n % 3 == 1; return ((2*$m-1)*(2*$n-1)+3)/6; # if $m % 3 == 2 || $n % 3 == 2 } return 2*$n if $m == 3; return $n == 3 ? 4 : $n if $m == 2; return $n >= 3 ? 2 : $n-1 if $m == 1; die "Bad call"; }
Formula
Exact for n <= 24, conjectured for n > 24 but it is at least a lower bound:
a(n) = 0 if n = 1.
a(n) = 2 if n = 2.
a(n) = 6 if n = 3.
a(n) = n*(2*n-1)/3 if n = 0 (mod 3) and n != 3.
a(n) = ((2n-1)^2+5)/6 if n = 1 (mod 3) and n != 1.
a(n) = ((2n-1)^2+3)/6 if n = 2 (mod 3).
Conjectures from Colin Barker, Jun 05 2019: (Start)
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).
a(n) = a(n-1) + 2*a(n-3) - 2*a(n-4) - a(n-6) + a(n-7) for n>9.
(End)
Comments