cp's OEIS Frontend

A131524 Number of possible palindromic rows (or columns) in an n X n crossword puzzle.

%I A131524 #21 May 06 2025 03:16:58
%S A131524 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 A131524 376,376,609,609,986,986,1596,1596,2583,2583,4180,4180,6764,6764,
%U A131524 10945,10945,17710,17710,28656,28656,46367,46367,75024,75024,121392,121392
%N A131524 Number of possible palindromic rows (or columns) in an n X n crossword puzzle.
%C A131524 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 A131524 Reinhard Zumkeller, <a href="/A131524/b131524.txt">Table of n, a(n) for n = 1..10000</a>
%H A131524 <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (1,1,-1,1,-1).
%F A131524 a(n+4) = a(n+2) + a(n) + 1, a(1) = a(2) = 0, a(3) = a(4) = 1.
%F A131524 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 A131524 O.g.f.: x^3/((1-x)*(1-x^2-x^4)). - _R. J. Mathar_, Dec 05 2007
%F A131524 a(2*n) = Fibonacci(n+1) - 1, a(2*n+1) = Fibonacci(n+2) - 1. - _G. C. Greubel_, Jul 13 2019
%e A131524 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 A131524 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 A131524 (Haskell)
%o A131524 import Data.List (transpose)
%o A131524 a131524 n = a131524_list !! (n-1)
%o A131524 a131524_list = concat $ transpose [tail a000071_list, tail a000071_list]
%o A131524 -- _Reinhard Zumkeller_, May 23 2013
%o A131524 (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 A131524 (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 A131524 (Sage)
%o A131524 def a(n):
%o A131524     if (n%2==0): return fibonacci((n+2)/2) -1
%o A131524     else: return fibonacci((n+3)/2) -1
%o A131524 [a(n) for n in (1..60)] # _G. C. Greubel_, Jul 13 2019
%o A131524 (GAP)
%o A131524 a:= function(n)
%o A131524     if n mod 2=0 then return Fibonacci(Int((n+2)/2)) -1;
%o A131524     else return Fibonacci(Int((n+3)/2)) -1;
%o A131524     fi;
%o A131524   end;
%o A131524 List([1..60], n-> a(n) ); # _G. C. Greubel_, Jul 13 2019
%Y A131524 Cf. A000045, A000071, A130578.
%K A131524 nonn,easy
%O A131524 1,5
%A A131524 Marc Brodie (mbrodie(AT)wju.edu), Aug 24 2007
%E A131524 More terms from _Robert G. Wilson v_, Aug 28 2007