login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A130578 Number of different possible rows (or columns) in an n X n crossword puzzle. 14
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,4

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.

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

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

EXAMPLE

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.

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"}}]

PROG

(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

(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

CROSSREFS

Sequence in context: A265073 A265074 A054886 * A107068 A033541 A038505

Adjacent sequences:  A130575 A130576 A130577 * A130579 A130580 A130581

KEYWORD

nonn,easy

AUTHOR

Marc A. Brodie (mbrodie(AT)wju.edu), Aug 10 2007, Aug 24 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 12 19:19 EST 2018. Contains 317116 sequences. (Running on oeis4.)