cp's OEIS Frontend

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

%I A221463 #8 Jun 02 2025 08:21:15
%S A221463 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,
%T A221463 36,150,384,513,240,13,0,8,49,252,875,1856,1944,656,21,0,9,64,392,
%U A221463 1728,5125,8960,7371,1792,34,0,10,81,576,3087,11880,30000,43264,27945,4896,55,0,11
%N A221463 T(n,k)=Number of 0..k arrays of length n with each element unequal to at least one neighbor, starting with 0.
%C A221463 Table starts
%C A221463 ..0.....0.......0........0.........0..........0..........0...........0
%C A221463 ..1.....2.......3........4.........5..........6..........7...........8
%C A221463 ..1.....4.......9.......16........25.........36.........49..........64
%C A221463 ..2....12......36.......80.......150........252........392.........576
%C A221463 ..3....32.....135......384.......875.......1728.......3087........5120
%C A221463 ..5....88.....513.....1856......5125......11880......24353.......45568
%C A221463 ..8...240....1944.....8960.....30000......81648.....192080......405504
%C A221463 .13...656....7371....43264....175625.....561168....1515031.....3608576
%C A221463 .21..1792...27945...208896...1028125....3856896...11949777....32112640
%C A221463 .34..4896..105948..1008640...6018750...26508384...94253656...285769728
%C A221463 .55.13376..401679..4870144..35234375..182191680..743424031..2543058944
%C A221463 .89.36544.1522881.23515136.206265625.1252200384.5863743809.22630629376
%H A221463 R. H. Hardin, <a href="/A221463/b221463.txt">Table of n, a(n) for n = 1..10000</a>
%F A221463 Recursion for column k:
%F A221463 k=1: a(n) = a(n-1) +a(n-2)
%F A221463 k=2: a(n) = 2*a(n-1) +2*a(n-2)
%F A221463 k=3: a(n) = 3*a(n-1) +3*a(n-2)
%F A221463 k=4: a(n) = 4*a(n-1) +4*a(n-2)
%F A221463 k=5: a(n) = 5*a(n-1) +5*a(n-2)
%F A221463 k=6: a(n) = 6*a(n-1) +6*a(n-2)
%F A221463 k=7: a(n) = 7*a(n-1) +7*a(n-2)
%F A221463 Empirical for row n:
%F A221463 n=2: a(k) = 1*k
%F A221463 n=3: a(k) = 1*k^2
%F A221463 n=4: a(k) = 1*k^3 + 1*k^2
%F A221463 n=5: a(k) = 1*k^4 + 2*k^3
%F A221463 n=6: a(k) = 1*k^5 + 3*k^4 + 1*k^3
%F A221463 n=7: a(k) = 1*k^6 + 4*k^5 + 3*k^4
%F A221463 n=8: a(k) = 1*k^7 + 5*k^6 + 6*k^5 + 1*k^4
%F A221463 n=9: a(k) = 1*k^8 + 6*k^7 + 10*k^6 + 4*k^5
%F A221463 n=10: a(k) = 1*k^9 + 7*k^8 + 15*k^7 + 10*k^6 + 1*k^5
%F A221463 n=11: a(k) = 1*k^10 + 8*k^9 + 21*k^8 + 20*k^7 + 5*k^6
%F A221463 n=12: a(k) = 1*k^11 + 9*k^10 + 28*k^9 + 35*k^8 + 15*k^7 + 1*k^6
%F A221463 n=13: a(k) = 1*k^12 + 10*k^11 + 36*k^10 + 56*k^9 + 35*k^8 + 6*k^7
%F A221463 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
%F A221463 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
%F A221463 Apparently then T(n,k) = sum { binomial(n-2-i,i)*k^(n-1-i) , 0<=2*i<=n-2 }.
%F A221463 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
%e A221463 Some solutions for n=6 k=4
%e A221463 ..0....0....0....0....0....0....0....0....0....0....0....0....0....0....0....0
%e A221463 ..4....2....1....3....3....2....2....1....4....2....3....1....3....2....3....3
%e A221463 ..1....4....0....1....2....4....3....0....2....0....3....3....2....0....0....4
%e A221463 ..0....0....3....4....2....3....2....1....0....3....2....4....3....3....4....1
%e A221463 ..1....2....1....2....1....0....3....4....0....1....3....1....3....0....2....0
%e A221463 ..0....3....2....3....3....1....4....0....4....2....0....0....0....4....0....3
%Y A221463 Column 1 is A000045(n-1)
%Y A221463 Column 2 is A028860(n+1)
%Y A221463 Column 3 is A106435(n-1)
%Y A221463 Column 4 is A094013
%Y A221463 Column 5 is A106565(n-1)
%Y A221463 Row 2 is A000027
%Y A221463 Row 3 is A000290
%Y A221463 Row 4 is A011379
%K A221463 nonn,tabl
%O A221463 1,5
%A A221463 _R. H. Hardin_, general recursion proved by _Robert Israel_ in the Sequence Fans Mailing List, Jan 17 2013