A189619 Number of 4 X n binary arrays without the pattern 0 1 0 diagonally, antidiagonally or horizontally.

16, 256, 1723, 8496, 50024, 357323, 2482591, 15915001, 100745265, 655633882, 4322765564, 28292943180, 183873191611, 1195974189947, 7802581300173, 50931021729006, 332106212299242, 2164490825527781, 14110729853099870

Offset

1,1

Links

R. H. Hardin, Table of n, a(n) for n = 1..200

Robert Israel, Maple-assisted proof of empirical recurrence

Formula

Empirical: a(n) = 8*a(n-1) -14*a(n-2) +10*a(n-3) +258*a(n-4) -737*a(n-5) -1502*a(n-6) +1780*a(n-7) +8033*a(n-8) -4800*a(n-9) -30115*a(n-10) +54016*a(n-11) -79554*a(n-12) -215482*a(n-13) +787373*a(n-14) -626468*a(n-15) -426934*a(n-16) +3545678*a(n-17) -6093224*a(n-18) +8409993*a(n-19) -6556066*a(n-20) +986540*a(n-21) -4549030*a(n-22) +9400135*a(n-23) -23776243*a(n-24) +29721357*a(n-25) -36187856*a(n-26) +30281962*a(n-27) -31933555*a(n-28) +10845312*a(n-29) +5786415*a(n-30) +7694508*a(n-31) +5236176*a(n-32) -9921669*a(n-33) -713908*a(n-34) +1520657*a(n-35) -3672439*a(n-36) +1127159*a(n-37) +4759522*a(n-38) -673175*a(n-39) -2818276*a(n-40) -151046*a(n-41) +1043153*a(n-42) +59137*a(n-43) -154754*a(n-44) -24424*a(n-45) +16833*a(n-46) +160*a(n-47) -631*a(n-48) -60*a(n-49) +4*a(n-50).

Empirical formula verified (see link). - Robert Israel, Oct 20 2019

Example

Some solutions for 4 X 3:
  1 1 1   0 0 0   1 1 0   1 1 0   1 1 0   1 1 0   0 0 1
  1 0 1   1 0 0   0 0 1   1 0 1   1 0 1   1 0 1   0 1 1
  1 1 1   1 0 1   0 0 0   1 0 0   1 0 0   0 0 0   1 0 1
  0 1 1   1 1 0   1 1 1   0 1 1   1 0 0   1 1 0   1 0 1

Maple

Configs:= [seq(convert(n, base, 2)[1..8], n=2^8..2^9-1)]:
Compatible:= proc(i, j) local Xi, Xj, k;
Xi:= Configs[i]; Xj:= Configs[j];
if Xi[5..8] <> Xj[1..4] then return 0 fi;
if Xi[1]=0 and ((Xi[5]=1 and Xj[5]=0) or (Xi[6]=1 and Xj[7]=0)) then return 0 fi;
if Xi[2]=0 and ((Xi[6]=1 and Xj[6]=0) or (Xi[7]=1 and Xj[8]=0)) then return 0 fi;
if Xi[3]=0 and ((Xi[6]=1 and Xj[5]=0) or (Xi[7]=1 and Xj[7]=0)) then return 0 fi;
if Xi[4]=0 and ((Xi[7]=1 and Xj[6]=0) or (Xi[8]=1 and Xj[8]=0)) then return 0 fi;
1
end proc:
T:= Matrix(256, 256, Compatible):
Tu[0]:= u:
for nn from 1 to 30 do Tu[nn]:= T . Tu[nn-1] od:
[16, seq(u^%T . Tu[n], n=0..30)]; # Robert Israel, Oct 20 2019

Crossrefs

Row 4 of A189617.

Sequence in context: A208366 A207714 A223671 * A189691 A188742 A296779

Adjacent sequences: A189616 A189617 A189618 * A189620 A189621 A189622

Keyword

nonn

Author

R. H. Hardin, Apr 24 2011

Status

approved