login
T(n,k)=Number of 0..k arrays of length n with each element differing from at least one neighbor by 2 or more, starting with 0
9

%I #4 Jan 18 2013 19:26:43

%S 0,0,0,0,1,0,0,2,1,0,0,3,3,2,0,0,4,7,12,3,0,0,5,13,36,30,5,0,0,6,21,

%T 80,130,89,8,0,0,7,31,150,381,532,248,13,0,0,8,43,252,884,1970,2088,

%U 706,21,0,0,9,57,392,1765,5513,9940,8304,1995,34,0,0,10,73,576,3174,12872,33860

%N T(n,k)=Number of 0..k arrays of length n with each element differing from at least one neighbor by 2 or more, starting with 0

%C Table starts

%C .0..0.....0.......0........0.........0..........0..........0...........0

%C .0..1.....2.......3........4.........5..........6..........7...........8

%C .0..1.....3.......7.......13........21.........31.........43..........57

%C .0..2....12......36.......80.......150........252........392.........576

%C .0..3....30.....130......381.......884.......1765.......3174........5285

%C .0..5....89.....532.....1970......5513......12872......26477.......49598

%C .0..8...248....2088.....9940.....33860......92934.....219352......463208

%C .0.13...706....8304....50495....208756.....672526....1819931.....4330224

%C .0.21..1995...32876...255980...1285694....4864004...15094631....40472105

%C .0.34..5652..130376..1298632...7921082...35184566..125207022...378288032

%C .0.55.15998..516704..6586395..48795589..254499831.1038541668..3535769160

%C .0.89.45297.2048264.33407907.300602292.1840896185.8614340129.33048102488

%H R. H. Hardin, <a href="/A221515/b221515.txt">Table of n, a(n) for n = 1..1574</a>

%F Empirical for column k:

%F k=2: a(n) = a(n-1) +a(n-2)

%F k=3: a(n) = a(n-1) +4*a(n-2) +3*a(n-3) +a(n-4)

%F k=4: a(n) = 2*a(n-1) +6*a(n-2) +6*a(n-3) +4*a(n-4) +4*a(n-6)

%F k=5: a(n) = 2*a(n-1) +11*a(n-2) +20*a(n-3) +17*a(n-4) -3*a(n-5) +a(n-6)

%F k=6: a(n) = 3*a(n-1) +14*a(n-2) +29*a(n-3) +28*a(n-4) +a(n-5) +27*a(n-6) +8*a(n-7) +2*a(n-8)

%F k=7: a(n) = 3*a(n-1) +21*a(n-2) +58*a(n-3) +79*a(n-4) +32*a(n-5) +23*a(n-6) +4*a(n-7) +8*a(n-8)

%F Empirical for row n:

%F n=2: a(k) = k - 1

%F n=3: a(k) = k^2 - 3*k + 3 for k>1

%F n=4: a(k) = k^3 - 2*k^2 + k

%F n=5: a(k) = k^4 - k^3 - 10*k^2 + 33*k - 34 for k>3

%F n=6: a(k) = k^5 - 20*k^3 + 78*k^2 - 146*k + 125 for k>4

%F n=7: a(k) = k^6 + k^5 - 29*k^4 + 104*k^3 - 173*k^2 + 136*k - 40 for k>3

%e Some solutions for n=6 k=4

%e ..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0

%e ..4....2....4....4....4....2....2....3....2....4....2....3....2....4....3....4

%e ..1....4....2....1....4....2....0....3....0....3....0....0....4....1....4....4

%e ..2....0....2....2....2....0....3....1....4....1....3....4....3....3....2....0

%e ..4....0....4....0....1....3....2....0....2....1....4....0....0....4....2....3

%e ..2....2....2....2....4....0....4....4....0....4....1....4....3....1....0....0

%Y Column 2 is A000045(n-1)

%Y Row 2 is A000027(n-1)

%Y Row 3 is A002061(n-1)

%Y Row 4 is A011379(n-1)

%K nonn,tabl

%O 1,8

%A _R. H. Hardin_ Jan 18 2013