A183307 Half the number of nX6 binary arrays with no element equal to a strict majority of its horizontal and vertical neighbors.

5, 14, 93, 572, 4212, 29400, 206755, 1447110, 10149621, 71244598, 500184679, 3512112015, 24658885220, 173129289198, 1215525172167, 8534122345666, 59917715208287, 420680331462689, 2953583636803146, 20737016295243029

Offset: 1

Author

R. H. Hardin Jan 03 2011

Keywords

• nonn

Comments

Column 6 of A183312

Examples

			Some solutions with a(1,1)=0 for 6X4
..0..0..1..0....0..1..0..1....0..1..0..1....0..1..0..0....0..1..0..1
..1..1..0..1....1..0..1..0....0..1..0..0....1..0..1..1....1..1..0..1
..0..1..0..0....1..0..0..1....1..0..1..1....0..0..1..0....0..0..1..0
..1..0..1..1....0..1..1..0....0..1..1..0....1..1..0..1....1..1..0..1
..0..1..0..0....1..0..0..1....1..0..0..1....0..1..0..0....0..0..1..0
..1..0..1..1....1..0..1..0....0..1..1..0....1..0..1..1....1..0..1..0
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..200
• Robert Israel, Linear recurrence of order 93
• Robert Israel, Maple-assisted derivation of recurrence

Programs

Maple

Allowed:= proc(a)
  if nops({a[1],a[2],a[7]})=1 or nops({a[1],a[2],a[3],a[8]})=1
  or nops({a[2],a[3],a[4],a[9]})=1 or nops({a[3],a[4],a[5],a[10]})=1
  or nops({a[4],a[5],a[6],a[11]})=1 or nops({a[5],a[6],a[12]})=1
  or nops({a[1],a[7],a[8]})=1 or nops({a[2],a[7],a[8],a[9]})=1
  or nops({a[3],a[8],a[9],a[10]})=1 or nops({a[4],a[9],a[10],a[11]})=1
  or nops({a[5],a[10],a[11],a[12]})=1 or nops({a[6],a[11],a[12]})=1
  then false else true fi
end proc:
Configs:= select(Allowed,[seq(convert(n,base,2)[1..12],n=2^12..2^13-1)]):
Compatible:= proc(i,j) local Xi,Xj,k;
 Xi:= map(t -> 2*t-1,Configs[i]); Xj:= map(t -> 2*t-1,Configs[j]);
 if Xi[7..12] <> Xj[1..6] then return 0 fi;
 if Xi[7] = signum(Xi[1]+Xi[8]+Xj[7]) then return 0 fi;
 for k from 8 to 11 do if Xi[k] = signum(Xi[k-6]+Xi[k-1]+Xi[k+1]+Xj[k]) then return 0 fi od;
 if Xi[12] = signum(Xi[6]+Xi[11]+Xj[12]) then return 0 fi;
 1
end proc:
T:= Matrix(722,722,Compatible):
uok:= proc(i) local a,k;
   a:= map(t -> 2*t-1, Configs[i]);
   for k from 2 to 5 do if a[k] = signum(a[k-1]+a[k+1]+a[k+6]) then return 0 fi od;
   1
end proc:
u:= Vector(722, uok):
vok:= proc(i) local a,k;
    a:= map(t -> 2*t-1, Configs[i]);
    for k from 8 to 11 do if a[k] = signum(a[k-1]+a[k+1]+a[k-6]) then return 0 fi od;
    1
end proc:
v:= Vector(722,vok):
Tv[0]:= v:
for nn from 1 to 50 do Tv[nn]:= T . Tv[nn-1] od:
A:= [10, seq(u^%T . Tv[n],n=0..50)]/2:
A[1..50]; # Robert Israel, Oct 23 2019

Formula

Linear recurrence of order 93 for n >= 95: see links. - Robert Israel, Oct 23 2019