A221683 T(n,k)=Number of 0..k arrays of length n with each element differing from at least one neighbor by 1 or less, starting with 0.

0, 0, 2, 0, 2, 4, 0, 2, 5, 8, 0, 2, 5, 14, 16, 0, 2, 5, 20, 40, 32, 0, 2, 5, 26, 68, 113, 64, 0, 2, 5, 32, 100, 241, 320, 128, 0, 2, 5, 38, 133, 418, 844, 906, 256, 0, 2, 5, 44, 166, 636, 1692, 2966, 2565, 512, 0, 2, 5, 50, 199, 891, 2856, 6932, 10413, 7262, 1024, 0, 2, 5, 56, 232

Offset: 1

Author

R. H. Hardin Jan 22 2013

Keywords

• nonn
• tabl

Comments

Table starts

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

....2.....2......2.......2.......2........2........2........2........2

....4.....5......5.......5.......5........5........5........5........5

....8....14.....20......26......32.......38.......44.......50.......56

...16....40.....68.....100.....133......166......199......232......265

...32...113....241.....418.....636......891.....1182.....1509.....1872

...64...320....844....1692....2856.....4326.....6102.....8184....10572

..128...906...2966....6932...13169....21985....33710....48674....67202

..256..2565..10413...28288...60120...109567...180382...276317...401105

..512..7262..36568..115604..275632...551027...980490..1606710..2476200

.1024.20560.128408..472188.1261451..2759757..5289023..9228224.15012528

.2048.58209.450913.1929012.5777107.13846871.28634131.53334307.91896348

Examples

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

Links

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

Crossrefs

Row 4 is A016933

Formula

Empirical for column k:

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

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

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

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

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

k=6: a(n) = 4*a(n-1) +5*a(n-2) -7*a(n-3) +33*a(n-4) +17*a(n-5) +24*a(n-6) -5*a(n-7) +2*a(n-8)

k=7: a(n) = 5*a(n-1) +3*a(n-2) -16*a(n-3) +65*a(n-4) -14*a(n-5) +23*a(n-6) +2*a(n-7) +8*a(n-8)

Empirical for row n:

n=1: a(n) = 0

n=2: a(n) = 2

n=3: a(n) = 5 for n>1

n=4: a(n) = 6*n + 2

n=5: a(n) = 33*n - 32 for n>3

n=6: a(n) = 18*n^2 + 57*n - 99 for n>4

n=7: a(n) = 153*n^2 - 213*n + 96 for n>3