|
|
A206451
|
|
Number of 0..4 arrays of length n avoiding the consecutive pattern 0..4
|
|
2
|
|
|
5, 25, 125, 625, 3124, 15615, 78050, 390125, 1950000, 9746876, 48718765, 243515775, 1217188750, 6083993750, 30410221874, 152002390605, 759768437250, 3797624997500, 18982040993750, 94879794746876, 474246971343775
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,1
|
|
COMMENTS
|
|
|
LINKS
|
|
|
FORMULA
|
a(n) = 5*a(n-1) -a(n-5)
Empirical: a(n) = sum{i in 0..floor(n/5)} ((-1)^i*5^(n-5*i)*binomial(n-4*i,i))
From Robert Israel, Jan 08 2016: (Start) The recursion can be proved using the matrix representation
a(n) = [ 1 1 1 1 1] M^n [ 1 0 0 0 0 ]^T, where
M = [ 4 3 3 3 3 ]
[ 1 1 1 1 1 ]
[ 0 1 0 0 0 ]
[ 0 0 1 0 0 ]
[ 0 0 0 1 0 ]
which satisfies M^5 = 5 M^4 - I.
G.f.: -x*(-5+x^4) / ( 1-5*x+x^5 ).. (End)
|
|
MAPLE
|
M:= <<4|3|3|3|3>, <1|1|1|1|1>, <0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>>:
seq(<1|1|1|1|1> . M^n . <1, 0, 0, 0, 0>, n=1..30); # Robert Israel, Jan 08 2016
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|