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!)
A133226 Number of possible 2 X n arrangements of black and white squares that can form two consecutive rows in an n X n crossword puzzle. 1
1, 9, 36, 98, 246, 646, 1777, 4883, 13120, 34642, 90976, 239160, 629427 (list; graph; refs; listen; history; text; internal format)
OFFSET

3,2

COMMENTS

In a standard American crossword puzzle, such as those in the New York Times, in any row there must be at least one run of white squares and all runs of white squares must be of length at least three.

LINKS

Table of n, a(n) for n=3..15.

FORMULA

a[n]=2a[n-1]-a[n-2]+a[n-3]+a[n-4]+f[n] where f[n]=b[n]^2-2b[n-1]^2+b[n-2]^2-b[n-3]^2-b[n-4]^2-2b[n-3] and b[n] is the sequence A130578

EXAMPLE

a[4]=9 = 3^2 because using 0's for white squares and 1's for black squares, the three possible rows in a 4 X 4 crossword are 0000, 1000 and 0001 and any of these three rows as a top row is compatible with any as a second row.

Furthermore, a[6]=98 < 100 = 10^2 because while 000111 and 111000 are two of the ten possible rows in a 6 X 6 crossword puzzle, the arrangement

000111

111000

would not be possible.

MATHEMATICA

<< DiscreteMath`Combinatorica` (*This program counts, lists and displays the possible 2 - row patterns in an n X n crossword puzzle*)

plotnice = ArrayPlot [ #, Frame -> False, Mesh -> True, MeshStyle -> GrayLevel [ 0 ] ] &;

For [ n = 3, n <= 7, n++,

usablemods = {0, 1, 3, 7};

usablenumbers = Function [ MemberQ [ usablemods, Mod [ #, 8 ] ] ];

goodnumbers = Union [ Table [

k, {k, 0, 2^(n - 3) - 1} ], Table [ k, {k, 2^(n - 1), 2^n - 2} ] ];

numbers = Select [ goodnumbers, usablenumbers ];

rows = Table [ PadLeft [ IntegerDigits [ numbers [ [ j ] ], 2 ], n ], {j, 1, Length [

numbers ]} ];

no101s = Function [ FreeQ [ Partition [ #1, 3, 1 ], {1, 0, 1} ] ];

no1001s = Function [ FreeQ [ Partition [ #1, 4, 1 ], {1, 0, 0, 1} ] ];

legalrows = Select [ Select [ rows, no1001s ], no101s ];

tworows = Tuples [ legalrows, 2 ];

addrows = Function [ Plus [ # [ [ 1 ] ], # [ [ 2 ] ] ] ];

goodrows = Function [ Not [ FreeQ [ Plus [ # [ [ 1 ] ], # [ [ 2 ] ] ], 0 ] ] ];

goodtworows = Select [ tworows, goodrows ];

Print [ "the number of two-row arrangements in a ", n, " x ", n, " puzzle is \

", Length [ goodtworows ] ];

plotnice /@ goodtworows;

]

CROSSREFS

Cf. A130578.

Sequence in context: A340965 A022604 A085630 * A027602 A231670 A134537

Adjacent sequences:  A133223 A133224 A133225 * A133227 A133228 A133229

KEYWORD

nonn

AUTHOR

Marc A. Brodie (mbrodie(AT)wju.edu), Jan 03 2008

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 May 15 07:17 EDT 2021. Contains 343909 sequences. (Running on oeis4.)