login
A239368
Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 1111.
2
1, 1, 4, 27, 252, 3020, 44220, 765030, 15269520, 345376080, 8730489600, 243911883600, 7463164262400, 248207881521600, 8915064168410400, 343923449355486000, 14182674669779616000, 622591172035376544000, 28986699477880400256000, 1426677017904959524704000
OFFSET
0,3
LINKS
FORMULA
Recursion: see Maple program.
MAPLE
a:= proc(n) option remember; `if`(n<3, n^n,
((105*n^3-252*n^2+175*n-36) *a(n-1) -2*(n-1)^2 *a(n-2)
+2*(5*n-2)*(n-1)^2*(n-2)^2*a(n-3)) / (4*(2*n-1)*(5*n-7)))
end:
seq(a(n), n=0..20); # Alois P. Heinz, Jul 20 2014
CROSSREFS
Sequence in context: A239377 A239371 A201996 * A245408 A243696 A158836
KEYWORD
nonn
AUTHOR
Chad Brewbaker, Mar 17 2014
EXTENSIONS
a(8)-a(11) from Alois P. Heinz, Mar 17 2014
a(12)-a(19) from Alois P. Heinz, Jul 20 2014
STATUS
approved