login
T(n,k) = Number of 0..k arrays of length n with each element differing from at least one neighbor by something other than 1, starting with 0.
10

%I #6 Oct 18 2017 18:22:05

%S 0,0,1,0,2,1,0,3,4,2,0,4,8,10,3,0,5,14,30,22,5,0,6,22,68,103,54,8,0,7,

%T 32,130,303,364,134,13,0,8,44,222,716,1386,1276,334,21,0,9,58,350,

%U 1455,4018,6311,4483,822,34,0,10,74,520,2658,9665,22466,28762,15740,2014,55,0,11

%N T(n,k) = Number of 0..k arrays of length n with each element differing from at least one neighbor by something other than 1, starting with 0.

%C Table starts

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

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

%C ..1.....4......8.......14........22........32.........44..........58

%C ..2....10.....30.......68.......130.......222........350.........520

%C ..3....22....103......303.......716......1455.......2658........4487

%C ..5....54....364.....1386......4018......9665......20386.......39007

%C ..8...134...1276.....6311.....22466.....64047.....156098......338711

%C .13...334...4483....28762....125701....424593....1195561.....2941622

%C .21...822..15740...131012....703193...2814515....9156379....25546512

%C .34..2014..55274...596784...3933916..18656979...70126074...221859676

%C .55..4934.194095..2718469..22007609.123673887..537074685..1926747595

%C .89.12110.681576.12383368.123117952.819813575.4113296146.16732904887

%H R. H. Hardin, <a href="/A221542/b221542.txt">Table of n, a(n) for n = 1..2080</a>

%F Empirical for column k:

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

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

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

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

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

%F k=6: a(n) = 7*a(n-1) -4*a(n-2) +6*a(n-3) +26*a(n-4) +10*a(n-5) +16*a(n-6) +12*a(n-8)

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

%F Empirical for row n:

%F n=2: a(n) = 1*n for n>1

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

%F n=4: a(n) = 1*n^3 + 1*n

%F n=5: a(n) = 1*n^4 + 1*n^3 - 3*n^2 + 10*n - 9 for n>3

%F n=6: a(n) = 1*n^5 + 2*n^4 - 6*n^3 + 21*n^2 - 31*n + 23 for n>4

%F n=7: a(n) = 1*n^6 + 3*n^5 - 8*n^4 + 25*n^3 - 30*n^2 + 20*n - 9 for n>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....2....3....2....0....4....0....4....4....3....4....0....4....4....4

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

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

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

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

%Y Column 1 is A000045(n-1).

%Y Row 2 is A000027.

%Y Row 3 is A003682.

%Y Row 4 is A034262.

%K nonn,tabl

%O 1,5

%A _R. H. Hardin_, Jan 19 2013