login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A131524 Number of possible palindromic rows (or columns) in an n X n crossword puzzle. 7
0, 0, 1, 1, 2, 2, 4, 4, 7, 7, 12, 12, 20, 20, 33, 33, 54, 54, 88, 88, 143, 143, 232, 232, 376, 376, 609, 609, 986, 986, 1596, 1596, 2583, 2583, 4180, 4180, 6764, 6764, 10945, 10945, 17710, 17710, 28656, 28656, 46367, 46367, 75024, 75024, 121392, 121392 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,5

COMMENTS

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)

LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000

Index entries for linear recurrences with constant coefficients, signature (1, 1, -1, 1, -1).

FORMULA

a(n+4) = a(n+2) + a(n) + 1, a(1) = a(2) = 0, a(3) = a(4) = 1.

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)).

O.g.f.: x^3/((1-x)*(1-x^2-x^4)). - R. J. Mathar, Dec 05 2007

a(2*n) = Fibonacci(n+1) - 1, a(2*n+1) = Fibonacci(n+2) - 1. - G. C. Greubel, Jul 13 2019

EXAMPLE

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

MATHEMATICA

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 *)

PROG

(Haskell)

import Data.List (transpose)

a131524 n = a131524_list !! (n-1)

a131524_list = concat $ transpose [tail a000071_list, tail a000071_list]

-- Reinhard Zumkeller, May 23 2013

(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

(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

(Sage)

def a(n):

    if (n%2==0): return fibonacci((n+2)/2) -1

    else: return fibonacci((n+3)/2) -1

[a(n) for n in (1..60)] # G. C. Greubel, Jul 13 2019

(GAP)

a:= function(n)

    if n mod 2=0 then return Fibonacci(Int((n+2)/2)) -1;

    else return Fibonacci(Int((n+3)/2)) -1;

    fi;

  end;

List([1..60], n-> a(n) ); # G. C. Greubel, Jul 13 2019

CROSSREFS

Cf. A000045, A000071, A130578.

Sequence in context: A062896 A025065 A306664 * A089075 A325098 A208963

Adjacent sequences:  A131521 A131522 A131523 * A131525 A131526 A131527

KEYWORD

nonn

AUTHOR

Marc Brodie (mbrodie(AT)wju.edu), Aug 24 2007

EXTENSIONS

More terms from Robert G. Wilson v, Aug 28 2007

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified April 1 02:00 EDT 2020. Contains 333153 sequences. (Running on oeis4.)