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

0, 0, 4, 0, 7, 8, 0, 10, 17, 16, 0, 13, 26, 49, 32, 0, 16, 35, 100, 139, 64, 0, 19, 44, 169, 342, 393, 128, 0, 22, 53, 256, 651, 1210, 1113, 256, 0, 25, 62, 361, 1068, 2715, 4240, 3151, 512, 0, 28, 71, 484, 1593, 5082, 11011, 14898, 8921, 1024, 0, 31, 80, 625, 2226, 8475

Offset: 1

Author

R. H. Hardin Jan 20 2013

Keywords

• nonn
• tabl

Comments

Table starts

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

....4......7......10.......13.......16........19........22........25.........28

....8.....17......26.......35.......44........53........62........71.........80

...16.....49.....100......169......256.......361.......484.......625........784

...32....139.....342......651.....1068......1593......2226......2967.......3816

...64....393....1210.....2715.....5082......8475.....13056.....18987......26430

..128...1113....4240....11011....22912.....41401.....67936....103975.....150976

..256...3151...14898....45099...105586....210101....374342....615965.....954572

..512...8921...52306...184063...482204...1047967...2006006...3504371....5714456

.1024..25257..183684...752155..2210256...5267759..10894988..20352239...35218688

.2048..71507..645006..3072247.10115926..26387005..58789204.116958723..213700742

.4096.202449.2264978.12550859.46327024.132384353.318224626.675761541.1307528098

Examples

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

Links

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

Crossrefs

Column 3 is A221568

Row 2 is A016777

Row 3 is A017257(n-1)

Row 4 is A016778

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) for n>4

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=2: a(n) = 3*n + 1

n=3: a(n) = 9*n - 1

n=4: a(n) = 9*n^2 + 6*n + 1

n=5: a(n) = 54*n^2 - 69*n + 63 for n>2

n=6: a(n) = 27*n^3 + 108*n^2 - 252*n + 267 for n>3

n=7: a(n) = 243*n^3 - 351*n^2 + 237*n + 127 for n>2