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

Author

Chad Brewbaker, Mar 17 2014

Keywords

• nonn

Links

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

Crossrefs

Cf. A012244, A239295.

Programs

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

Formula

Recursion: see Maple program.

Extensions

a(8)-a(11) from Alois P. Heinz, Mar 17 2014

a(12)-a(19) from Alois P. Heinz, Jul 20 2014