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

Author

Alois P. Heinz, Oct 26 2016

Keywords

• nonn
• tabl

Examples

			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, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..140, flattened
• Sela Fried, Toufik Mansour, and Mark Shattuck, Counting k-ary words by number of adjacency differences of a prescribed size, arXiv:2504.03013 [math.CO], 2025. See p. 6.

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.

Programs

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 *)

Formula

G.f. of column k: 1/(1 + Sum_{j=1..k} (k+1-j)*(-x)^j).