A188818 Number of n X n binary arrays without the pattern 0 1 diagonally or antidiagonally.

1, 2, 9, 48, 256, 1360, 7056, 36000, 179776, 884256, 4276624, 20432608, 96353856, 449990080, 2080089664, 9540782208, 43403888896, 196212020800, 881112632976, 3936117388896, 17487049789504, 77350773736512, 340574032803904, 1493986588951168, 6528047911024896

Offset: 0

Author

R. H. Hardin, Apr 11 2011

Keywords

• nonn

Examples

			Some solutions for 3X3:
  0  1  0    1  1  1    1  1  1    1  0  1    1  0  1    1  0  1    1  1  0
  1  0  0    1  1  0    0  1  0    0  1  0    0  1  0    0  1  0    1  0  1
  0  0  0    1  0  1    0  0  0    1  0  1    0  0  0    1  0  0    0  0  0
		

Links

• Manuel Kauers and Christoph Koutschan, Table of n, a(n) for n = 0..1000 (terms 1..32 from R. H. Hardin).
• M. Kauers and C. Koutschan, Some D-finite and some possibly D-finite sequences in the OEIS, arXiv:2303.02793 [cs.SC], 2023.

Crossrefs

Diagonal of A188824.

Programs

Mathematica

Prepend[Table[(2^(n - 2) + 2*Sum[Binomial[n - 1, n - k - l] - Binomial[n - 1, n + k - l + 1], {k, 0, Floor[(n + 1)/2]}, {l, k + 1, Floor[(n + 1)/2]}]) * (2^(n - 2) + 2*Sum[Binomial[n - 1, n - k - l - 1] - Binomial[n - 1, n + k - l + 1], {k, 0, Floor[n/2]}, {l, k + 1, Floor[n/2]}]), {n, 2, 100}], 2] (* Manuel Kauers and Christoph Koutschan, Mar 02 2023 *)

Formula

From Manuel Kauers and Christoph Koutschan, Mar 02 2023: (Start)

a(n) = (2^(n-2) + 2*Sum_{k=0..floor((n+1)/2)} Sum_{l=k+1..floor((n+1)/2)} binomial(n-1, n-k-l) - binomial(n-1, n+k-l+1)) * (2^(n-2) + 2*Sum_{k=0..floor(n/2)} Sum_{l=k+1..floor(n/2)} binomial(n-1, n-k-l-1) - binomial(n-1, n+k-l+1)) for n>1.

Recurrence: (n-2)*(n+3)^2*(n+4)*(2*n^6 - 3*n^5 - 22*n^4 - 17*n^3 - 16*n^2 - 61*n - 33)*a(n+5) - 4*(n+3)*(2*n^9 + 15*n^8 - 24*n^7 - 278*n^6 - 279*n^5 + 622*n^4 + 1327*n^3 + 1792*n^2 + 2619*n + 1314)*a(n+4) - 16*(n+2)*(4*n^9 + 8*n^8 - 91*n^7 - 251*n^6 + 183*n^5 + 509*n^4 - 1161*n^3 - 1955*n^2 - 399*n - 207)*a(n+3) + 64*(4*n^10 + 32*n^9 + 17*n^8 - 455*n^7 - 1362*n^6 - 754*n^5 + 2250*n^4 + 4669*n^3 + 5364*n^2 + 4509*n + 1566)*a(n+2) + 256*(n+1)*(2*n^9 + n^8 - 52*n^7 - 121*n^6 + 79*n^5 + 255*n^4 - 476*n^3 - 1533*n^2 - 1665*n - 810)*a(n+1) - 1024*(n-1)*n*(n+1)^2*(2*n^6 + 9*n^5 - 7*n^4 - 95*n^3 - 199*n^2 - 235*n - 150)*a(n) = 0. (End)

Extensions

a(0)=1 prepended by Alois P. Heinz, Mar 02 2023