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,3

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

Links

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

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

Example

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

Crossrefs

Row 4 is A016933

Sequence in context: A117946 A061930 A209691 * A332760 A199335 A141660

Adjacent sequences: A221680 A221681 A221682 * A221684 A221685 A221686

Keyword

nonn,tabl

Author

R. H. Hardin Jan 22 2013

Status

approved