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

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

Links

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

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

Example

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

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)

Sequence in context: A034365 A103778 A099423 * A221984 A071920 A306548

Adjacent sequences: A221512 A221513 A221514 * A221516 A221517 A221518

Keyword

nonn,tabl

Author

R. H. Hardin Jan 18 2013

Status

approved