A221463 T(n,k)=Number of 0..k arrays of length n with each element unequal to at least one neighbor, starting with 0.

0, 0, 1, 0, 2, 1, 0, 3, 4, 2, 0, 4, 9, 12, 3, 0, 5, 16, 36, 32, 5, 0, 6, 25, 80, 135, 88, 8, 0, 7, 36, 150, 384, 513, 240, 13, 0, 8, 49, 252, 875, 1856, 1944, 656, 21, 0, 9, 64, 392, 1728, 5125, 8960, 7371, 1792, 34, 0, 10, 81, 576, 3087, 11880, 30000, 43264, 27945, 4896, 55, 0, 11

Offset: 1

Author

R. H. Hardin, general recursion proved by Robert Israel in the Sequence Fans Mailing List, Jan 17 2013

Keywords

• nonn
• tabl

Comments

Table starts

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

..1.....2.......3........4.........5..........6..........7...........8

..1.....4.......9.......16........25.........36.........49..........64

..2....12......36.......80.......150........252........392.........576

..3....32.....135......384.......875.......1728.......3087........5120

..5....88.....513.....1856......5125......11880......24353.......45568

..8...240....1944.....8960.....30000......81648.....192080......405504

.13...656....7371....43264....175625.....561168....1515031.....3608576

.21..1792...27945...208896...1028125....3856896...11949777....32112640

.34..4896..105948..1008640...6018750...26508384...94253656...285769728

.55.13376..401679..4870144..35234375..182191680..743424031..2543058944

.89.36544.1522881.23515136.206265625.1252200384.5863743809.22630629376

Examples

			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....1....3....3....2....2....1....4....2....3....1....3....2....3....3
..1....4....0....1....2....4....3....0....2....0....3....3....2....0....0....4
..0....0....3....4....2....3....2....1....0....3....2....4....3....3....4....1
..1....2....1....2....1....0....3....4....0....1....3....1....3....0....2....0
..0....3....2....3....3....1....4....0....4....2....0....0....0....4....0....3
		

Links

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

Crossrefs

Column 1 is A000045(n-1)

Column 2 is A028860(n+1)

Column 3 is A106435(n-1)

Column 4 is A094013

Column 5 is A106565(n-1)

Row 2 is A000027

Row 3 is A000290

Row 4 is A011379

Formula

Recursion for column k:

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

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

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

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

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

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

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

Empirical for row n:

n=2: a(k) = 1*k

n=3: a(k) = 1*k^2

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

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

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

n=7: a(k) = 1*k^6 + 4*k^5 + 3*k^4

n=8: a(k) = 1*k^7 + 5*k^6 + 6*k^5 + 1*k^4

n=9: a(k) = 1*k^8 + 6*k^7 + 10*k^6 + 4*k^5

n=10: a(k) = 1*k^9 + 7*k^8 + 15*k^7 + 10*k^6 + 1*k^5

n=11: a(k) = 1*k^10 + 8*k^9 + 21*k^8 + 20*k^7 + 5*k^6

n=12: a(k) = 1*k^11 + 9*k^10 + 28*k^9 + 35*k^8 + 15*k^7 + 1*k^6

n=13: a(k) = 1*k^12 + 10*k^11 + 36*k^10 + 56*k^9 + 35*k^8 + 6*k^7

n=14: a(k) = 1*k^13 + 11*k^12 + 45*k^11 + 84*k^10 + 70*k^9 + 21*k^8 + 1*k^7

n=15: a(k) = 1*k^14 + 12*k^13 + 55*k^12 + 120*k^11 + 126*k^10 + 56*k^9 + 7*k^8

Apparently then T(n,k) = sum { binomial(n-2-i,i)*k^(n-1-i) , 0<=2*i<=n-2 }.

The formula reduces to T(n,k) = [4*k^(n-1)*(1+G)^(2*n-2) +4^n] /[2^(n+1) *G *(1+G)^(n-1)] for even n and to T(n,k) = [4*k^(n-1) *(1+G)^(2*n-2) -4^n] /[2^(n+1) *G *(1+G)^(n-1)] for odd n, where G=sqrt(1+4/k). - R. J. Mathar, Jan 21 2013