[seqfan] Re: a(n)= k * ( a(n-1) + a(n-2)), numerology and formula

[israel at math.ubc.ca]

The recurrence arises as follows: An allowed array of length n starting 
with 0 can have one of the two forms 0 x L where x <> 0 and L is an allowed 
array of length n-2 starting with x, or 0 L where L is an allowed array of 
length n-1 starting with a nonzero element.

Robert Israel
University of British Columbia

On Jan 14 2013, Ron Hardin wrote:

>Empirical formula at end
>
>/tmp/cxn
>T(n,k)=Number of 0..k arrays of length n starting with 0 with each element 
>unequal to at least one neighbor
>
>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
>
>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
>
> Empirical 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 }
>
>
>
> rhhardin at mindspring.com
>rhhardin at att.net (either)
>
>
>_______________________________________________
>
>Seqfan Mailing list - http://list.seqfan.eu/
>
>