A185830 Half the number of n X 4 binary arrays with every element equal to exactly one or two of its horizontal and vertical neighbors.
2, 23, 118, 514, 2398, 11789, 54223, 257050, 1213538, 5716561, 26960702, 127201987, 599792318, 2828918061, 13342117403, 62924057051, 296766436047, 1399631468891, 6601012746804, 31132105093032, 146827124366034, 692474808791206
Offset: 1
Keywords
Examples
Some solutions for 6 X 4 with a(1,1)=0: 0 0 0 0 0 0 1 1 0 0 1 0 0 1 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 1 0 0 1 0 0 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 0 1 1 0 1 1 0 1 0 1 0 1 0 0 1 1 0 1 1 1 1 0 1 0 1 0 0 1 0 1 0 1 0 1 0 1 0 0 0 0 1 0 1 0 0 1 1 0 0 0 1 1 0 1 0 1 1 1 1 0 1 1 1 0 0 1 1 0
Links
- R. H. Hardin, Table of n, a(n) for n = 1..200
- Robert Israel, Maple-assisted proof of formula
Crossrefs
Cf. A185835.
Programs
-
Maple
Configs:= remove(t -> min(nops({t[1],t[2],t[3],t[6]}), nops({t[2],t[3],t[4],t[7]}), nops({t[2],t[5],t[6],t[7]}), nops({t[3],t[6],t[7],t[8]}))=1, [seq(convert(2^8+i,base,2)[1..8],i=0..2^8-1)]): Compatible:= proc(i,j) local k; if Configs[i][5..8] <> Configs[j][1..4] or not member(numboccur(Configs[i][5], [Configs[i][1],Configs[i][6],Configs[j][5]]),{1,2}) or not member(numboccur(Configs[i][6], [Configs[i][2],Configs[i][5],Configs[i][7],Configs[j][6]]),{1,2}) or not member(numboccur(Configs[i][7], [Configs[i][3],Configs[i][6],Configs[i][8],Configs[j][7]]),{1,2}) or not member(numboccur(Configs[i][8], [Configs[i][4],Configs[i][7],Configs[j][8]]),{1,2}) then 0 else 1 fi; end proc: T:= Matrix(162,162,Compatible): u:= Vector(162,proc(i) if member(numboccur(Configs[i][1],[Configs[i][2],Configs[i][5]]),{1,2}) and member(numboccur(Configs[i][2],[Configs[i][1],Configs[i][3],Configs[i][6]]),{1,2}) and member(numboccur(Configs[i][3],[Configs[i][2],Configs[i][4],Configs[i][7]]),{1,2}) and member(numboccur(Configs[i][4],[Configs[i][3],Configs[i][8]]),{1,2}) then 1 else 0 fi end proc) : v:= Vector(162,proc(i) if member(numboccur(Configs[i][5],[Configs[i][1],Configs[i][6]]),{1,2}) and member(numboccur(Configs[i][6],[Configs[i][2],Configs[i][5],Configs[i][7]]),{1,2}) and member(numboccur(Configs[i][7],[Configs[i][3],Configs[i][6],Configs[i][8]]),{1,2}) and member(numboccur(Configs[i][8],[Configs[i][4],Configs[i][7]]),{1,2}) then 1 else 0 fi end proc) : Tv[0]:= v: for n from 1 to 50 do Tv[n]:= T . Tv[n-1] od: [2, seq(u^%T . Tv[n]/2,n=0..50)]; # Robert Israel, Aug 15 2018
Formula
Empirical: a(n) = 4*a(n-1) + 9*a(n-2) - 15*a(n-3) - 67*a(n-4) + 2*a(n-5) + 321*a(n-6) - 70*a(n-7) - 672*a(n-8) - 351*a(n-9) + 920*a(n-10) - 5077*a(n-11) + 733*a(n-12) + 28694*a(n-13) + 15849*a(n-14) - 28046*a(n-15) - 56805*a(n-16) + 89957*a(n-17) - 87270*a(n-18) + 85004*a(n-19) - 164885*a(n-20) + 188247*a(n-21) - 111655*a(n-22) + 89028*a(n-23) - 117971*a(n-24) + 115994*a(n-25) - 64896*a(n-26) + 52709*a(n-27) - 50206*a(n-28) + 31595*a(n-29) - 11233*a(n-30) + 1156*a(n-31) + 2585*a(n-32) - 5924*a(n-33) + 2841*a(n-34) - 817*a(n-35) + 361*a(n-36) - 42*a(n-37) - 6*a(n-38).
Empirical formula verified (see link). - Robert Israel, Aug 15 2018
Comments