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

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, 80, 130, 89, 8, 0, 0, 7, 31, 150, 381, 532, 248, 13, 0, 0, 8, 43, 252, 884, 1970, 2088, 706, 21, 0, 0, 9, 57, 392, 1765, 5513, 9940, 8304, 1995, 34, 0, 0, 10, 73, 576, 3174, 12872, 33860

Offset: 1

Author

R. H. Hardin Jan 18 2013

Keywords

• nonn
• tabl

Comments

Table starts

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

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

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

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

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

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

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

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

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

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

.0.55.15998..516704..6586395..48795589..254499831.1038541668..3535769160

.0.89.45297.2048264.33407907.300602292.1840896185.8614340129.33048102488

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....4....4....4....2....2....3....2....4....2....3....2....4....3....4
..1....4....2....1....4....2....0....3....0....3....0....0....4....1....4....4
..2....0....2....2....2....0....3....1....4....1....3....4....3....3....2....0
..4....0....4....0....1....3....2....0....2....1....4....0....0....4....2....3
..2....2....2....2....4....0....4....4....0....4....1....4....3....1....0....0
		

Links

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

Crossrefs

Column 2 is A000045(n-1)

Row 2 is A000027(n-1)

Row 3 is A002061(n-1)

Row 4 is A011379(n-1)

Formula

Empirical for column k:

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

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

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

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)

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)

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)

Empirical for row n:

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

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

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

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

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

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