A130578 Number of different possible rows (or columns) in an n X n crossword puzzle.

0, 0, 1, 3, 6, 10, 16, 26, 43, 71, 116, 188, 304, 492, 797, 1291, 2090, 3382, 5472, 8854, 14327, 23183, 37512, 60696, 98208, 158904, 257113, 416019, 673134, 1089154, 1762288, 2851442, 4613731, 7465175, 12078908, 19544084

Offset: 1

Author

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

Keywords

• nonn
• easy

Comments

The number of linear arrangements of n black and white squares subject to the conditions that there must be at least one run of white squares and all runs of white squares must be of length at least three.

Crossword puzzles such as those in the New York Times do not include one-letter or two-letter words. Since the daily NYT puzzle is 15 X 15, there are a(15) = 797 different possible arrangements for each row.

Examples

			a(5) = 6 because using 0's for white squares and 1's for black, the possible rows are: 00011, 10001, 11000, 00001, 10000, 00000.
		

Links

• Reinhard Zumkeller, Table of n, a(n) for n = 1..5000
• Fumio Hazama, Spectra of graphs attached to the space of melodies, Discr. Math., 311 (2011), 2368-2383. See Table 2.1.
• Index entries for linear recurrences with constant coefficients, signature (3,-3,1,1,-1).

Programs

Haskell

a130578 n = a130578_list !! (n-1)
a130578_list = 0 : 0 : 1 : 3 : zipWith (+)
   (map (* 2) $ drop 3 a130578_list)
   (zipWith (-) (map (+ 1) a130578_list) (drop 2 a130578_list))
-- Reinhard Zumkeller, May 23 2013

Mathematica

possiblerows = {}; For[n = 1, n <= 36, n++, table = Table[{n, k, Coefficient[(x^0 + Sum[x^i, {i, 3, n - k}])^(k + 1), x, n - k]}, {k, 0, n}]; total = Sum[table[[j, 3]], {j, 1, n}]; possiblerows = Append[possiblerows, total]; totalstable = Table[{t, possiblerows[[t]]}, {t, 1, Length[ possiblerows]}]]; TableForm[totalstable, TableHeadings -> {None, {" n = squares", "total number of permissible rows"}}]

PARI

a(n)=([0,1,0,0,0;0,0,1,0,0;0,0,0,1,0;0,0,0,0,1;-1,1,1,-3,3]^n*[0;0;0;1;3])[1,1] \\ Charles R Greathouse IV, Jun 11 2015

Formula

Recurrence: a(n+4) = 2*a(n+3) - a(n+2) + a(n) + 1, with a(1) = 0, a(2) = 0, a(3) = 1, a(4) = 3.

Formula: a(n) = (30 - 30*sqrt(5) - 30*(1/2 - sqrt(5)/2)^n + 12*sqrt(5)*(1/2 - sqrt(5)/2)^n + 15*(1/2 + sqrt(5)/2)^n + 3*sqrt(5)*(1/2 + sqrt(5)/2)^n - 15*cos((n*Pi)/3) + 15*sqrt(5)*cos((n*Pi)/3) + 5*sqrt(3)*sin((n*Pi)/3) - 5*sqrt(15)*sin((n*Pi)/3))/(30*(-1 + sqrt(5))).

O.g.f.: x^3/((-1+x)*(x^2+x-1)*(x^2-x+1)). - R. J. Mathar, Nov 23 2007

a(n) = A005252(n+1) - 1. - R. J. Mathar, Nov 15 2011

G.f.: Q(0)*x^2/(2-2*x), where Q(k) = 1 + 1/(1 - x*( 4*k+2 -x +x^3)/( x*( 4*k+4 -x +x^3) +1/Q(k+1) )); (continued fraction). - Sergei N. Gladkovskii, Jan 07 2014