%I #18 Sep 08 2022 08:45:31
%S 0,0,1,1,2,2,4,4,7,7,12,12,20,20,33,33,54,54,88,88,143,143,232,232,
%T 376,376,609,609,986,986,1596,1596,2583,2583,4180,4180,6764,6764,
%U 10945,10945,17710,17710,28656,28656,46367,46367,75024,75024,121392,121392
%N Number of possible palindromic rows (or columns) in an n X n crossword puzzle.
%C To be an acceptable row, there must be at least one run of white squares and all runs of white squares must be of length at least three. Palindromic rows are of interest since if n is odd, the middle row of an n x n crossword puzzle must be palindromic if the puzzle is to have to usual rotational symmetry. Rather than use the explicit formula above, it is perhaps easier to observe that for all m, a(2m) = a(2m-1) and thus both the subsequences of odd-numbered terms and even-numbered terms are Fibonacci numbers - 1. (see A000071)
%H Reinhard Zumkeller, <a href="/A131524/b131524.txt">Table of n, a(n) for n = 1..10000</a>
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1, 1, -1, 1, -1).
%F a(n+4) = a(n+2) + a(n) + 1, a(1) = a(2) = 0, a(3) = a(4) = 1.
%F a(n) = (2^(-n/2) (-5*2^(n/2)*(-1 + sqrt(5))^(3/2) + sqrt(5)*(1 + sqrt(5))^(n/2) (-sqrt(2)*(-1 + (-1)^n) + (1 + (-1)^n) sqrt(-1 + sqrt(5))) + 2 (-1 + sqrt(5))^(n/2) (sqrt(-55 + 25 sqrt(5)) cos(n Pi)/2 + sqrt(2) (-5 + 2 sqrt(5)) sin(n Pi)/2))))/(5 (-1 + sqrt(5))^(3/2)).
%F O.g.f.: x^3/((1-x)*(1-x^2-x^4)). - _R. J. Mathar_, Dec 05 2007
%F a(2*n) = Fibonacci(n+1) - 1, a(2*n+1) = Fibonacci(n+2) - 1. - _G. C. Greubel_, Jul 13 2019
%e a(9) = 7 because the palindromic rows, using 0's for white squares and 1's for black, are: 000000000, 100000001, 110000011, 111000111, 000010000, 000111000, 100010001
%t With[{F=Fibonacci}, Table[If[Mod[n,2]==0, F[(n+2)/2] -1, F[(n+3)/2] -1], {n, 60}]] (* _G. C. Greubel_, Jul 13 2019 *)
%o (Haskell)
%o import Data.List (transpose)
%o a131524 n = a131524_list !! (n-1)
%o a131524_list = concat $ transpose [tail a000071_list, tail a000071_list]
%o -- _Reinhard Zumkeller_, May 23 2013
%o (PARI) vector(60, n, f=fibonacci; if(n%2==0, f((n+2)/2)-1, f((n+3)/2)-1)) \\ _G. C. Greubel_, Jul 13 2019
%o (Magma) F:=Fibonacci; [(n mod 2) eq 0 select F(floor((n+2)/2))-1 else F(Floor((n+3)/2))-1: n in [1..60]]; // _G. C. Greubel_, Jul 13 2019
%o (Sage)
%o def a(n):
%o if (n%2==0): return fibonacci((n+2)/2) -1
%o else: return fibonacci((n+3)/2) -1
%o [a(n) for n in (1..60)] # _G. C. Greubel_, Jul 13 2019
%o (GAP)
%o a:= function(n)
%o if n mod 2=0 then return Fibonacci(Int((n+2)/2)) -1;
%o else return Fibonacci(Int((n+3)/2)) -1;
%o fi;
%o end;
%o List([1..60], n-> a(n) ); # _G. C. Greubel_, Jul 13 2019
%Y Cf. A000045, A000071, A130578.
%K nonn
%O 1,5
%A Marc Brodie (mbrodie(AT)wju.edu), Aug 24 2007
%E More terms from _Robert G. Wilson v_, Aug 28 2007