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.

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

Alois P. Heinz, Antidiagonals n = 0..140, flattened

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: A339779 A277504 A167763 * A274581 A353279 A321919

Adjacent sequences: A277663 A277664 A277665 * A277667 A277668 A277669

Keyword

nonn,tabl

Author

Alois P. Heinz, Oct 26 2016

Status

approved