|
|
A277673
|
|
Number of n-length words over an n-ary alphabet {a_1,a_2,...,a_n} avoiding consecutive letters a_i, a_{i+1}.
|
|
2
|
|
|
1, 1, 3, 16, 136, 1547, 22012, 375231, 7445184, 168412696, 4275561136, 120338946469, 3718175865856, 125094920949797, 4551798150123456, 178094082550301368, 7455514741874966528, 332495821030327545527, 15737024371475868676864, 787813565550480151088691
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,3
|
|
LINKS
|
|
|
FORMULA
|
a(n) = [x^n] 1/(1+Sum_{j=1..n} (n+1-j)*(-x)^j).
|
|
EXAMPLE
|
a(3) = 16: 000, 002, 020, 021, 022, 100, 102, 110, 111, 200, 202, 210, 211, 220, 221, 222 (using ternary alphabet {0, 1, 2}).
|
|
MAPLE
|
b:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
-add((-1)^j*(k+1-j)*b(n-j, k), j=1..k)))
end:
a:= n-> b(n$2):
seq(a(n), n=0..25);
|
|
MATHEMATICA
|
b[n_, k_] := b[n, k] = If[n < 0, 0, If[n == 0, 1,
-Sum[(-1)^j (k+1-j) b[n-j, k], {j, 1, k}]]];
a[n_] := b[n, n];
|
|
CROSSREFS
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|