OFFSET
0,3
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..200
FORMULA
a(n) = Sum_{i=0...ceiling(n/2)} (n-1)^(n-i)*binomial(n-1+1,i). Each term in the summation enumerates the number of such words containing exactly i 1's where 0<=i<=ceiling(n/2). Write down n-i letters that are not 1's leaving a space before and after every letter. Choose i of the n - i + 1 spaces in which to insert a 1.
a(n) ~ n^n. - Vaclav Kotesovec, Dec 21 2012
EXAMPLE
a(3) = 22 because there are 27 3-letter words on {1,2,3} but 5 of these are "bad": 111, 112, 113, 211, 311.
MAPLE
b:= proc(n, k, w) option remember; `if`(n=0, 1,
`if`(w, 0, b(n-1, k, true))+ (k-1)*b(n-1, k, false))
end:
a:= n-> b(n, n, false):
seq (a(n), n=0..30); # Alois P. Heinz, Dec 20 2012
MATHEMATICA
ReplacePart[Table[Sum[Binomial[n-i+1, i] (n-1)^(n-i), {i, 0, Ceiling[n/2]}], {n, 0, 20}], 2->1]
CROSSREFS
KEYWORD
nonn
AUTHOR
Geoffrey Critzer, Dec 19 2012
STATUS
approved