A221542 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.

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, 32, 130, 303, 364, 134, 13, 0, 8, 44, 222, 716, 1386, 1276, 334, 21, 0, 9, 58, 350, 1455, 4018, 6311, 4483, 822, 34, 0, 10, 74, 520, 2658, 9665, 22466, 28762, 15740, 2014, 55, 0, 11

Offset: 1

Author

R. H. Hardin, Jan 19 2013

Keywords

• nonn
• tabl

Comments

Table starts

..0.....0......0........0.........0.........0..........0...........0

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

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

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

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

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

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

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

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

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

.55..4934.194095..2718469..22007609.123673887..537074685..1926747595

.89.12110.681576.12383368.123117952.819813575.4113296146.16732904887

Examples

			Some solutions for n=6 k=4
..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
..4....2....2....3....2....0....4....0....4....4....3....4....0....4....4....4
..0....4....4....4....0....2....3....2....3....0....0....4....2....1....4....4
..0....0....0....4....4....4....1....3....1....4....2....2....0....1....2....0
..3....2....4....4....4....0....0....3....1....1....4....4....4....2....0....0
..0....2....1....2....0....2....2....3....3....1....4....2....0....0....0....3
		

Links

• R. H. Hardin, Table of n, a(n) for n = 1..2080

Crossrefs

Column 1 is A000045(n-1).

Row 2 is A000027.

Row 3 is A003682.

Row 4 is A034262.

Formula

Empirical for column k:

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

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

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

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

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

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)

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)

Empirical for row n:

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

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

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

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

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

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