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

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

Links

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

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

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

Crossrefs

Column 1 is A000045(n-1).

Row 2 is A000027.

Row 3 is A003682.

Row 4 is A034262.

Sequence in context: A166040 A106378 A094301 * A221463 A135488 A099493

Adjacent sequences: A221539 A221540 A221541 * A221543 A221544 A221545

Keyword

nonn,tabl

Author

R. H. Hardin, Jan 19 2013

Status

approved