A181252 Number of n X 9 binary matrices with no 2 X 2 block having four 1's.

512, 169209, 61986457, 22161786304, 7969215344753, 2861765993703849, 1027999596778673856, 369248337357375835969, 132633131268024896655873, 47641303155727829675539968, 17112587585474467714330327353

Offset: 1

Author

R. H. Hardin, Oct 10 2010

Keywords

• nonn

Comments

Column 9 of A181253.

Links

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

Crossrefs

Cf. A181253.

Programs

Maple

for i from 1 to 512 do Configs[i]:= convert(2^9+i-1,base,2)[1..9] od:
Compatible:= proc(i,j)
if `and`(seq(evalb(Configs[i][k] + Configs[i][k+1] + Configs[j][k]+Configs[j][k+1] < 4), k=1..8)) then 1 else 0 fi
end proc:
T:= Matrix(512,512,Compatible):
v:= Vector(512,1):
TV[0]:= v:
for nn from 1 to 23 do TV[nn]:= T . TV[nn-1] od:
seq(v^%T . TV[n],n=0..23); # Robert Israel, Apr 02 2020

Formula

Linear recurrence of order 48: see link. - Robert Israel, Apr 02 2020