login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A189619 Number of 4 X n binary arrays without the pattern 0 1 0 diagonally, antidiagonally or horizontally. 1
16, 256, 1723, 8496, 50024, 357323, 2482591, 15915001, 100745265, 655633882, 4322765564, 28292943180, 183873191611, 1195974189947, 7802581300173, 50931021729006, 332106212299242, 2164490825527781, 14110729853099870 (list; graph; refs; listen; history; text; internal format)
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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 6 05:39 EDT 2022. Contains 355108 sequences. (Running on oeis4.)