A239368 Number of words of length n over the alphabet {0,...,n-1} that avoid the pattern 1111.

1, 1, 4, 27, 252, 3020, 44220, 765030, 15269520, 345376080, 8730489600, 243911883600, 7463164262400, 248207881521600, 8915064168410400, 343923449355486000, 14182674669779616000, 622591172035376544000, 28986699477880400256000, 1426677017904959524704000

Offset

0,3

Links

Alois P. Heinz, Table of n, a(n) for n = 0..350

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

Cf. A012244, A239295.

Sequence in context: A239377 A239371 A201996 * A245408 A243696 A158836

Adjacent sequences: A239365 A239366 A239367 * A239369 A239370 A239371

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