login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

T(n,k) = number of (n+2) X (k+2) binary matrices with every 3 X 3 block having exactly four 1's.
9

%I #22 Feb 08 2023 00:05:40

%S 126,336,336,906,746,906,2484,1684,1684,2484,7218,3942,3190,3942,7218,

%T 21024,10348,6360,6360,10348,21024,61398,27554,14974,10818,14974,

%U 27554,61398,182520,74784,36244,22512,22512,36244,74784,182520,542754,212570,91122,48846,41374,48846,91122,212570,542754

%N T(n,k) = number of (n+2) X (k+2) binary matrices with every 3 X 3 block having exactly four 1's.

%C Table starts:

%C 126 336 906 2484 7218 21024 61398 182520 542754

%C 336 746 1684 3942 10348 27554 74784 212570 608476

%C 906 1684 3190 6360 14974 36244 91122 247372 681262

%C 2484 3942 6360 10818 22512 48846 112500 289830 764832

%C 7218 10348 14974 22512 41374 79324 162882 387076 952462

%C 21024 27554 36244 48846 79324 133850 242784 526226 1196428

%C 61398 74784 91122 112500 162882 242784 386406 750312 1548594

%C 182520 212570 247372 289830 387076 526226 750312 1297322 2384308

%C 542754 608476 681262 764832 952462 1196428 1548594 2384308 3873790

%C 1614492 1755630 1906656 2072106 2438184 2877078 3449484 4777806 6881880

%H R. H. Hardin, <a href="/A181262/b181262.txt">Table of n, a(n) for n=1..219</a>

%H David Radcliffe, <a href="/A181262/a181262.pdf">Counting binary matrices with every 3 X 3 block having exactly four ones</a>

%F Empirical column 1: a(n) = 3*a(n-1) + 12*a(n-3) - 36*a(n-4) - 27*a(n-6) + 81*a(n-7).

%F Empirical column 2: a(n) = 4*a(n-1) - 3*a(n-2) + 32*a(n-3) - 128*a(n-4) + 96*a(n-5) - 375*a(n-6) + 1500*a(n-7) - 1125*a(n-8) + 1980*a(n-9) - 7920*a(n-10) + 5940*a(n-11) - 4644*a(n-12) + 18576*a(n-13) - 13932*a(n-14) + 3888*a(n-15) - 15552*a(n-16) + 11664*a(n-17).

%F Empirical columns 3 and 4: a(n) = 4*a(n-1) - 3*a(n-2) + 36*a(n-3) - 144*a(n-4) + 108*a(n-5) - 503*a(n-6) + 2012*a(n-7) - 1509*a(n-8) + 3480*a(n-9) - 13920*a(n-10) + 10440*a(n-11) - 12564*a(n-12) + 50256*a(n-13) - 37692*a(n-14) + 22464*a(n-15) - 89856*a(n-16) + 67392*a(n-17) - 15552*a(n-18) + 62208*a(n-19) - 46656*a(n-20).

%F Empirical columns 5 and 6: a(n) = 6*a(n-1) - 11*a(n-2) + 42*a(n-3) - 216*a(n-4) + 396*a(n-5) - 719*a(n-6) + 3018*a(n-7) - 5533*a(n-8) + 6498*a(n-9) - 20880*a(n-10) + 38280*a(n-11) - 33444*a(n-12) + 75384*a(n-13) - 138204*a(n-14) + 97848*a(n-15) - 134784*a(n-16) + 247104*a(n-17) - 150336*a(n-18) + 93312*a(n-19) - 171072*a(n-20) + 93312*a(n-21).

%F All columns (provably) satisfy a(n) = 6*a(n-1) - 11*a(n-2) + 60*a(n-3) - 324*a(n-4) + 594*a(n-5) - 1475*a(n-6) + 6906*a(n-7) - 12661*a(n-8) + 19440*a(n-9) - 75204*a(n-10) + 137874*a(n-11) - 150408*a(n-12) + 451224*a(n-13) - 827244*a(n-14) + 699840*a(n-15) - 1491696*a(n-16) + 2734776*a(n-17) - 1911600*a(n-18) + 2519424*a(n-19) - 4618944*a(n-20) + 2799360*a(n-21) - 1679616*a(n-22) + 3079296*a(n-23) - 1679616*a(n-24). The characteristic polynomial for this recurrence is (x - 1)*(x - 2)*(x - 3)*(x^3 - 2)*(x^3 - 3)*(x^3 - 4)*(x^3 - 6)*(x^3 - 9)*(x^3 - 12)*(x^3 - 18). - _David Radcliffe_, Jan 14 2023

%e Some solutions for 3 X 3:

%e 1 1 0 0 0 1 1 0 0 1 0 0 1 1 0 0 1 0 0 0 0

%e 0 1 1 1 1 0 1 1 1 0 1 1 0 0 1 0 0 1 0 0 1

%e 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 1 1 1 1 1

%Y Cf. A181256, A181257, A181258, A181259, A181260, A181261 for columns 1-6.

%K nonn,tabl

%O 1,1

%A _R. H. Hardin_, Oct 10 2010