# Greetings from The On-Line Encyclopedia of Integer Sequences! http://oeis.org/

Search: id:a133226
Showing 1-1 of 1

%I A133226 #2 Feb 27 2009 03:00:00
%S A133226 1,9,36,98,246,646,1777,4883,13120,34642,90976,239160,629427
%N 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.
%C A133226 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.
%F A133226 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
%e A133226 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.
%e A133226 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
%e A133226 000111
%e A133226 111000
%e A133226 would not be possible.
%t A133226 << DiscreteMath`Combinatorica` (*This program counts, lists and displays the possible 2 - row patterns in an n X n crossword puzzle*)
%t A133226 plotnice = ArrayPlot [ #, Frame -> False, Mesh -> True, MeshStyle -> GrayLevel [ 0 ] ] &;
%t A133226 For [ n = 3, n <= 7, n++,
%t A133226 usablemods = {0, 1, 3, 7};
%t A133226 usablenumbers = Function [ MemberQ [ usablemods, Mod [ #, 8 ] ] ];
%t A133226 goodnumbers = Union [ Table [
%t A133226 k, {k, 0, 2^(n - 3) - 1} ], Table [ k, {k, 2^(n - 1), 2^n - 2} ] ];
%t A133226 numbers = Select [ goodnumbers, usablenumbers ];
%t A133226 rows = Table [ PadLeft [ IntegerDigits [ numbers [ [ j ] ], 2 ], n ], {j, 1, Length [
%t A133226 numbers ]} ];
%t A133226 no101s = Function [ FreeQ [ Partition [ #1, 3, 1 ], {1, 0, 1} ] ];
%t A133226 no1001s = Function [ FreeQ [ Partition [ #1, 4, 1 ], {1, 0, 0, 1} ] ];
%t A133226 legalrows = Select [ Select [ rows, no1001s ], no101s ];
%t A133226 tworows = Tuples [ legalrows, 2 ];
%t A133226 addrows = Function [ Plus [ # [ [ 1 ] ], # [ [ 2 ] ] ] ];
%t A133226 goodrows = Function [ Not [ FreeQ [ Plus [ # [ [ 1 ] ], # [ [ 2 ] ] ], 0 ] ] ];
%t A133226 goodtworows = Select [ tworows, goodrows ];
%t A133226 Print [ "the number of two-row arrangements in a ", n, " x ", n, " puzzle is \
%t A133226 ", Length [ goodtworows ] ];
%t A133226 plotnice /@ goodtworows;
%t A133226 ]
%Y A133226 Cf. A130578.
%K A133226 nonn
%O A133226 3,2
%A A133226 Marc A. Brodie (mbrodie(AT)wju.edu), Jan 03 2008

# Content is available under The OEIS End-User License Agreement: http://oeis.org/LICENSE