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

%I #22 Mar 07 2023 07:35:42

%S 1,2,9,48,256,1360,7056,36000,179776,884256,4276624,20432608,96353856,

%T 449990080,2080089664,9540782208,43403888896,196212020800,

%U 881112632976,3936117388896,17487049789504,77350773736512,340574032803904,1493986588951168,6528047911024896

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

%H Manuel Kauers and Christoph Koutschan, <a href="/A188818/b188818.txt">Table of n, a(n) for n = 0..1000</a> (terms 1..32 from R. H. Hardin).

%H M. Kauers and C. Koutschan, <a href="https://arxiv.org/abs/2303.02793">Some D-finite and some possibly D-finite sequences in the OEIS</a>, arXiv:2303.02793 [cs.SC], 2023.

%F From _Manuel Kauers_ and _Christoph Koutschan_, Mar 02 2023: (Start)

%F 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.

%F 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)

%e Some solutions for 3X3:

%e 0 1 0 1 1 1 1 1 1 1 0 1 1 0 1 1 0 1 1 1 0

%e 1 0 0 1 1 0 0 1 0 0 1 0 0 1 0 0 1 0 1 0 1

%e 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0

%t 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 *)

%Y Diagonal of A188824.

%K nonn

%O 0,2

%A _R. H. Hardin_, Apr 11 2011

%E a(0)=1 prepended by _Alois P. Heinz_, Mar 02 2023