login
A277666
Number A(n,k) of n-length words over a k-ary alphabet {a_1,a_2,...,a_k} avoiding consecutive letters a_i, a_{i+1}; square array A(n,k), n>=0, k>=0, read by antidiagonals.
10
1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 3, 1, 0, 1, 4, 7, 4, 1, 0, 1, 5, 13, 16, 5, 1, 0, 1, 6, 21, 42, 37, 6, 1, 0, 1, 7, 31, 88, 136, 86, 7, 1, 0, 1, 8, 43, 160, 369, 440, 200, 8, 1, 0, 1, 9, 57, 264, 826, 1547, 1423, 465, 9, 1, 0, 1, 10, 73, 406, 1621, 4264, 6486, 4602, 1081, 10, 1, 0
OFFSET
0,8
LINKS
FORMULA
G.f. of column k: 1/(1 + Sum_{j=1..k} (k+1-j)*(-x)^j).
EXAMPLE
A(3,3) = 16: 000, 002, 020, 021, 022, 100, 102, 110, 111, 200, 202, 210, 211, 220, 221, 222 (using ternary alphabet {0, 1, 2}).
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 1, 3, 7, 13, 21, 31, 43, ...
0, 1, 4, 16, 42, 88, 160, 264, ...
0, 1, 5, 37, 136, 369, 826, 1621, ...
0, 1, 6, 86, 440, 1547, 4264, 9953, ...
0, 1, 7, 200, 1423, 6486, 22012, 61112, ...
0, 1, 8, 465, 4602, 27194, 113632, 375231, ...
MAPLE
A:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
-add((-1)^j*(k+1-j)*A(n-j, k), j=1..k)))
end:
seq(seq(A(n, d-n), n=0..d), d=0..14);
MATHEMATICA
A[n_, k_] := A[n, k] = If[n < 0, 0, If[n == 0, 1, -Sum[(-1)^j*(k + 1 - j)* A[n-j, k], {j, 1, k}]]];
Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jun 08 2018, from Maple *)
CROSSREFS
Columns k=0-10 give: A000007, A000012, A000027(n+1), A095263(n+1), A277667, A277668, A277669, A277670, A277671, A277672, A096261.
Rows n=0-2 give: A000012, A001477, A002061 (for k>0).
Main diagonal gives A277673.
Sequence in context: A373424 A277504 A167763 * A274581 A353279 A321919
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Oct 26 2016
STATUS
approved