1,4

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.

Recurrence: a[n + 4] == 2 a[n + 3] - a[n + 2] + a[n] + 1, 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 (mathar(AT)strw.leidenuniv.nl), Nov 23 2007

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

Clear[k]; Clear[n]; 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"}}]

Adjacent sequences: A130575 A130576 A130577 this_sequence A130579 A130580 A130581

Sequence in context: A025004 A114324 A054886 this_sequence A107068 A033541 A038505

nonn

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