OFFSET
0,2
COMMENTS
Number of binary arrangements without adjacent 1's on n X n array connected nw-se.
Kitaev and Mansour give a general formula for the number of binary m X n matrices avoiding certain configurations.
LINKS
Reinhard Zumkeller, Table of n, a(n) for n = 0..68
Sergey Kitaev and Toufik Mansour, The problem of the pawns, arXiv:math/0305253 [math.CO], 2003; Annals of Combinatorics 8 (2004) 81-91.
Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69, 421.
FORMULA
a(n) = (F(3) * F(4) * ... * F(n+1))^2 * F(n+2), where F(n) = A000045(n) is the n-th Fibonacci number.
a(n) is asymptotic to C^2*((1+sqrt(5))/2)^((n+2)^2)/(5^(n+3/2)) where C=1.226742010720353244... is the Fibonacci Factorial Constant, see A062073. - Vaclav Kotesovec, Oct 28 2011
a(n) = a(n-1) * A001654(n+1), n > 0. - Reinhard Zumkeller, Sep 24 2015
EXAMPLE
Neighbors for n=4 (dots represent spaces, circles represent grid points):
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O
.\..\..\..
..\..\..\.
O..O..O..O
MAPLE
a:= proc(n) option remember; `if`(n=0, 1, (F->
F(n+1)*F(n+2)*a(n-1))(combinat[fibonacci]))
end:
seq(a(n), n=0..14); # Alois P. Heinz, May 20 2019
MATHEMATICA
Rest[Table[With[{c=Fibonacci[Range[n]]}, (Times@@Most[c])^2 Last[c]], {n, 15}]] (* Harvey P. Dale, Dec 17 2013 *)
PROG
(PARI) a(n)=fibonacci(n+2)*prod(i=0, n, fibonacci(i+1))^2
(Haskell)
a067962 n = a067962_list !! n
a067962_list = 1 : zipWith (*) a067962_list (drop 2 a001654_list)
-- Reinhard Zumkeller, Sep 24 2015
CROSSREFS
Cf. circle A000204, line A000045, arrays: ne-sw nw-se A067965, e-w ne-sw nw-se A067963, n-s nw-se A067964, e-w n-s nw-se A066864, e-w ne-sw n-s nw-se A063443, n-s A067966, e-w n-s A006506, toruses: bare A002416, ne-sw nw-se A067960, ne-sw n-s nw-se A067959, e-w ne-sw n-s nw-se A067958, n-s A067961, e-w n-s A027683, e-w ne-sw n-s A066866.
KEYWORD
nonn,nice
AUTHOR
R. H. Hardin, Feb 02 2002
EXTENSIONS
Edited by Dean Hickerson, Feb 15 2002
Revised by N. J. A. Sloane following comments from Benoit Cloitre, Nov 12 2003
STATUS
approved