|
|
A190526
|
|
Number of words of length n on alphabet {1,2,...,n} with no adjacent 1's.
|
|
1
|
|
|
1, 1, 3, 22, 216, 2704, 41125, 736344, 15171919, 353603584, 9197472240, 264121100000, 8299793401537, 283296166612992, 10437388463753355, 412833263709870976, 17448273126337500000, 784766322909932158976, 37424980125359271911917, 1886309447532093698360832
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
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.
|
|
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):
|
|
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
|
|
|
STATUS
|
approved
|
|
|
|