A130578 -id:A130578 - cp's OEIS frontend

A131524 Number of possible palindromic rows (or columns) in an n X n crossword puzzle.

0, 0, 1, 1, 2, 2, 4, 4, 7, 7, 12, 12, 20, 20, 33, 33, 54, 54, 88, 88, 143, 143, 232, 232, 376, 376, 609, 609, 986, 986, 1596, 1596, 2583, 2583, 4180, 4180, 6764, 6764, 10945, 10945, 17710, 17710, 28656, 28656, 46367, 46367, 75024, 75024, 121392, 121392

Offset: 1

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

To be an acceptable row, there must be at least one run of white squares and all runs of white squares must be of length at least three. Palindromic rows are of interest since if n is odd, the middle row of an n x n crossword puzzle must be palindromic if the puzzle is to have to usual rotational symmetry. Rather than use the explicit formula above, it is perhaps easier to observe that for all m, a(2m) = a(2m-1) and thus both the subsequences of odd-numbered terms and even-numbered terms are Fibonacci numbers - 1. (see A000071)

			a(9) = 7 because the palindromic rows, using 0's for white squares and 1's for black, are: 000000000, 100000001, 110000011, 111000111, 000010000, 000111000, 100010001

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (1,1,-1,1,-1).

Cf. A000045, A000071, A130578.

a:= function(n)
    if n mod 2=0 then return Fibonacci(Int((n+2)/2)) -1;
    else return Fibonacci(Int((n+3)/2)) -1;
    fi;
  end;
List([1..60], n-> a(n) ); # G. C. Greubel, Jul 13 2019

import Data.List (transpose)
a131524 n = a131524_list !! (n-1)
a131524_list = concat $ transpose [tail a000071_list, tail a000071_list]
-- Reinhard Zumkeller, May 23 2013

F:=Fibonacci; [(n mod 2) eq 0 select F(floor((n+2)/2))-1 else F(Floor((n+3)/2))-1: n in [1..60]]; // G. C. Greubel, Jul 13 2019

With[{F=Fibonacci}, Table[If[Mod[n,2]==0, F[(n+2)/2] -1, F[(n+3)/2] -1], {n, 60}]] (* G. C. Greubel, Jul 13 2019 *)

vector(60, n, f=fibonacci; if(n%2==0, f((n+2)/2)-1, f((n+3)/2)-1)) \\ G. C. Greubel, Jul 13 2019

def a(n):
    if (n%2==0): return fibonacci((n+2)/2) -1
    else: return fibonacci((n+3)/2) -1
[a(n) for n in (1..60)] # G. C. Greubel, Jul 13 2019

a(n+4) = a(n+2) + a(n) + 1, a(1) = a(2) = 0, a(3) = a(4) = 1.
a(n) = (2^(-n/2) (-5*2^(n/2)*(-1 + sqrt(5))^(3/2) + sqrt(5)*(1 + sqrt(5))^(n/2) (-sqrt(2)*(-1 + (-1)^n) + (1 + (-1)^n) sqrt(-1 + sqrt(5))) + 2 (-1 + sqrt(5))^(n/2) (sqrt(-55 + 25 sqrt(5)) cos(n Pi)/2 + sqrt(2) (-5 + 2 sqrt(5)) sin(n Pi)/2))))/(5 (-1 + sqrt(5))^(3/2)).
O.g.f.: x^3/((1-x)*(1-x^2-x^4)). - R. J. Mathar, Dec 05 2007
a(2*n) = Fibonacci(n+1) - 1, a(2*n+1) = Fibonacci(n+2) - 1. - G. C. Greubel, Jul 13 2019

More terms from Robert G. Wilson v, Aug 28 2007

A132443 Number of n x n crossword puzzles with rotational symmetry and exactly one black square per row.

Original entry on oeis.org

0, 0, 0, 2, 2, 10, 12, 120, 186

Offset: 3

Marc Brodie (mbrodie(AT)wju.edu), Aug 21 2007

nonn

Acceptable crossword puzzles must have all words of length 3 or more, at least one word in each row and each column and be connected.

			a(6) = 2 because the only two 6 X 6 crossword puzzles are (using 1's for black squares and 0's for white):
100000
100000
100000
000001
000001
000001
and
000001
000001
000001
100000
100000
100000

Marc Brodie, Mathematica program

Cf. A130578, A132444, A132445, A132446.

A132445 Number of n X n crossword puzzles with rotational symmetry and at most one black square per row.

Original entry on oeis.org

1, 3, 5, 7, 16, 47, 135, 643

Offset: 3

Marc Brodie (mbrodie(AT)wju.edu), Aug 21 2007

nonn

Acceptable crossword puzzles must have all words of length 3 or more, at least one word in each row and each column and be connected.

			a(5) = 5 because the only acceptable 5 X 5 crossword puzzles are (using 1's for black squares and 0's for white) are:
00000 10000 10000 00001 00001
00000 00000 10000 00000 00001
00000 00000 00000 00000 00000
00000 00000 00001 00000 10000
00000 00001 00001 10000 10000

Marc Brodie, Mathematica program

Cf. A130578, A132443, A132444, A132446.

A132446 The number of n x n crossword puzzles with at most one black square per row up to horizontal/vertical symmetry.

Original entry on oeis.org

1, 2, 3, 4, 10, 24, 71, 322

Offset: 3

Marc Brodie (mbrodie(AT)wju.edu), Aug 21 2007, Aug 22 2007

nonn

Acceptable crossword puzzles must have all words of length 3 or more, at least one word in each row and each column and be connected.

			a(5) = 3 because up to symmetry the only 5 x 5 acceptable crossword puzzles with at most one black square per row (using 1's for black squares and 0's for white) are:
00000 10000 10000
00000 00000 10000
00000 00000 00000
00000 00000 00001
00000 00001 00001

Marc Brodie, Mathematica program

Cf. A130578, A132443, A132444, A132445.

A132444 Number of n x n crossword puzzles with rotational symmetry and exactly one black square per row, up to symmetry.

Original entry on oeis.org

0, 0, 0, 1, 1, 5, 6, 60, 93

Offset: 3

Marc Brodie (mbrodie(AT)wju.edu), Aug 21 2007

nonn

Acceptable crossword puzzles must have all words of length 3 or more, at least one word in each row and each column and be connected. Since the puzzles counted in sequence A132443 come naturally in pairs (by reflective symmetry), the numbers in this sequence are obtained by dividing the corresponding numbers in A132443 by 2.

			a(6) = 1 because up to symmetry, the only 6 X 6 crossword puzzle with exactly one black square in each row (using 1's for black squares and 0's for white) is:
100000
100000
100000
000001
000001
000001

Cf. A130578, A132443, A132445, A132446.

Maple
```
See the program for A132443
```

A209232 a(n) is 2^n times the expected value of the shortest run of 0's in a binary word of length n.

Original entry on oeis.org

0, 1, 4, 11, 25, 52, 103, 199, 380, 724, 1382, 2649, 5103, 9881, 19224, 37559, 73646, 144848, 285623, 564429, 1117396, 2215436, 4398054, 8740266, 17385207, 34607218, 68934319, 137386725, 273942683, 546450648, 1090419638

Offset: 0

Geoffrey Critzer, Jan 12 2013

nonn

a(n) is also the sum of the number of binary words containing at least one 0 and having every consecutive run of 0's of length >= i for i >= 1. In other words, a(n) = A000225(n) + A077855(n) + A130578(n) + A209231(n) + ...

			a(3) = 11. To the length 3 binary words {0, 0, 0}, {0, 0, 1}, {0, 1, 0}, {0, 1, 1}, {1, 0, 0}, {1, 0, 1}, {1, 1, 0}, {1, 1, 1} we have respectively shortest zero runs of length 3 + 2 + 1 + 1 + 2 + 1 + 1 + 0 = 11.

R. Sedgewick and P. Flajolet, Analysis of Algorithms, Addison Wesley, 1996, Chapter 7.

G. C. Greubel, Table of n, a(n) for n = 0..1000

Cf. A119706.

nn = 30; Apply[Plus, Table[a = x^n/(1 - x); CoefficientList[Series[(a + 1)/((1 - a x/(1 - x)))*1/(1 - x) - 1/(1 - x), {x, 0, nn}], x], {n, 1, nn}]]

O.g.f.: Sum_{k >= 1} (x^k/(1 - x) + 1) / ((1 - x^(k + 1)/(1 - x)^2)) * 1/(1 - x) - 1/(1 - x).

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.

Original entry on oeis.org

1, 9, 36, 98, 246, 646, 1777, 4883, 13120, 34642, 90976, 239160, 629427

Offset: 3

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

nonn

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.

			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.

Cf. A130578.

<< 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;
]

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

A133253 Number of possible 3 X n arrangements of black and white squares that can form three consecutive rows in an n X n crossword puzzle.

Original entry on oeis.org

1, 23, 159, 649, 2424, 9574, 39913, 166639, 678898

Offset: 3

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

nonn

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.

Cf. A130578.

< 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 ];
threerows = Tuples [ legalrows, 3 ];
transposedthreerows = Transpose /@ threerows;
freeof101s = Function [ FreeQ [ #, {1, 0, 1} ] ];
transposedno101s = Select [ transposedthreerows, freeof101s ];
legalthreerows = Transpose /@ transposedno101s;
insertzerorows = Function [ Append [ Prepend [ #, Table [ 0, {n} ] ], Table [ 0, {n} ] ] ];
legalthreerowswithzeros = insertzerorows /@ legalthreerows;
finalthreerows = {};
legalthreerowscount = 0;
For [ v = 1, v <= Length [ legalthreerowswithzeros ], v++,
puzzlegraph = Table [ legalthreerowswithzeros [ [ v, r, s ] ], {r,
1, 5}, {s, 1, n} ];
verts = {};
For [ i2 =
1, i2 <= 5, i2++, For [ j2 = 1, j2
<= n, j2++, If [ puzzlegraph [ [ i2, j2 ] ] == 1, verts = Append [
verts, j2 + 5n - n*i2 ] ] ] ];
thegraph = DeleteVertices [ GridGraph [ n, 5 ], verts ];
If [ ConnectedQ [ thegraph ] == True, connectedcount = connectedcount + 1 ];
(*graph = ShowGraph [ thegraph, DisplayFunction -> Identity ];
thepuzzle = ArrayPlot [ legalthreerowswithzeros [ [ v ] ], Frame -> False,
Mesh -> True, MeshStyle -> GrayLevel [
0 ], DisplayFunction -> Identity ];*)
(*Show [ GraphicsArray [ {thepuzzle, graph} ] ];*)
(*Print [ ConnectedQ [ thegraph ] ];*)
If [ ConnectedQ [ thegraph ] == True, legalthreerowscount = \
legalthreerowscount +
1; finalthreerows = Append [ finalthreerows, legalthreerows [ [ v ] ] ] ];
]
plotnice /@ finalthreerows;
Print [ "the number of threerow arrangements in a ", n, " x ", n, " puzzle is ", legalthreerowscount ] ]

A133258 Number of possible 3 X n arrangements of black and white squares that can form the middle three rows in an n X n crossword puzzle with rotational symmetry. In this sequence, n is ODD.

Original entry on oeis.org

1, 11, 38, 157, 718, 3039, 12571

Offset: 3

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

For this sequence, n must be odd.

Cf. A130578.

(*This program counts, lists and displays the possible three - row centers \ of an n X n (n odd) crossword puzzle with rotational symmetry.*)
plotnice = ArrayPlot [ #, Frame -> False, Mesh -> True, MeshStyle -> \
GrayLevel [ 0 ] ] &;
For [ w = 1, w <= 7, w++,
n = 2w + 1;
t = n - 3;
arrangements = {};
For [ r = 0, r <= t, r++,
m = Compositions [ n - r, r + 1 ];
m2 = Select [ m, FreeQ [ #, 2 ] & ];
m1 = Select [ m2, FreeQ [ #, 1 ] & ];
arrangements = Join [ arrangements, m1 ] ];
possiblecolumns = {};
For [ j = 1, j <= Length [ arrangements ], j++,
original = arrangements [ [ j ] ];
new = {};
For [ i = 1, i <= Length [ original ], i++, new = Append [ new,
Join [ Table [ 0, {original [ [ i ] ]} ], {1} ] ] ];
new = Drop [ Flatten [ new ], -1 ];
possiblecolumns = Append [ possiblecolumns, new ] ];
symmetricrows =
Select [ possiblecolumns,
possiblecolumns [ [ # ] ] == Reverse [ possiblecolumns [ [ # ] ] ] & ];
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 ];
reversedlegalrows = Reverse /@ legalrows;
potentialcenters = Flatten [ Table [ {legalrows [ [ i ] ], symmetricrows [ [ j ] ],
reversedlegalrows [ [ i ] ]}, {i, 1,
Length [ legalrows ]}, {j, 1, Length [ symmetricrows ]} ], 1 ];
transposedpotentialcenters = Transpose /@ potentialcenters;
freeof101s = Function [ FreeQ [ #, {1, 0, 1} ] ];
transposedno101s = Select [ transposedpotentialcenters, freeof101s ];
almostcenters = Transpose /@ transposedno101s;
insertzerorows =
Function [ Append [ Prepend [ #, Table [ 0, {n} ] ], Table [ 0, {n} ] ] ];
almostcenterswithzeros = insertzerorows /@ almostcenters;
centers = {};
centercount = 0;
For [ v = 1, v <= Length [ almostcenterswithzeros ], v++,
puzzlegraph = Table [ almostcenterswithzeros [ [ v, r, s ] ], {r, 1, 5}, {s,
1, n} ];
verts = {};
For [ i2 = 1, i2 <= 5, i2++, For [ j2 = 1, j2 <= n, j2++, If [ puzzlegraph [ [ i2,
j2 ] ] == 1, verts = Append [ verts, j2 + 5n - n*i2 ] ] ] ];
thegraph = DeleteVertices [ GridGraph [ n, 5 ], verts ];
If [ ConnectedQ [ thegraph ] ==
True, centercount = centercount + 1;
centers = Append [ centers, almostcenterswithzeros [ [ v ] ] ] ];
]
plotnice /@ centers;
Print [ "the number of center three-row arrangements in a ", n, " x ", n, " puzzle with rotational symmetry is ", centercount ];
Print [ " " ];
]

A137334 Number of n X n crossword puzzles with dihedral symmetry group, for n odd. Acceptable crossword puzzles must have all words of length 3 or more, at least one word in each row and each column and be connected.

Original entry on oeis.org

1, 2, 10, 45, 302, 3102, 45795

Offset: 3

Marc Brodie (mbrodie(AT)wju.edu), Apr 07 2008

nonn

The number of such puzzles for an even n = 2m is equal to the number of (2m-1) X (2m-1) puzzles.

			a(5) = 2 because, using 0's for white squares and 1's for black squares, the only two 5 X 5 puzzles with dihedral symmetry group are:
00000
00000
00000
00000
00000
and
10001
00000
00000
00000
10001

Marc Brodie, Mathematica program

Cf. A130578, A133226, A133253, A133258.

cp's OEIS Frontend

A131524 Number of possible palindromic rows (or columns) in an n X n crossword puzzle.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Haskell

Magma

Mathematica

PARI

Sage

Formula

Extensions

A132443 Number of n x n crossword puzzles with rotational symmetry and exactly one black square per row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132445 Number of n X n crossword puzzles with rotational symmetry and at most one black square per row.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132446 The number of n x n crossword puzzles with at most one black square per row up to horizontal/vertical symmetry.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A132444 Number of n x n crossword puzzles with rotational symmetry and exactly one black square per row, up to symmetry.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A209232 a(n) is 2^n times the expected value of the shortest run of 0's in a binary word of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A133253 Number of possible 3 X n arrangements of black and white squares that can form three consecutive rows in an n X n crossword puzzle.

Views

Author

Keywords

Comments

Crossrefs

Programs