cp's OEIS Frontend

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.

%I A277666 #17 Apr 07 2025 09:50:00
%S A277666 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,
%T A277666 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,
%U A277666 264,826,1547,1423,465,9,1,0,1,10,73,406,1621,4264,6486,4602,1081,10,1,0
%N 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.
%H A277666 Alois P. Heinz, <a href="/A277666/b277666.txt">Antidiagonals n = 0..140, flattened</a>
%H A277666 Sela Fried, Toufik Mansour, and Mark Shattuck, <a href="https://arxiv.org/abs/2504.03013">Counting k-ary words by number of adjacency differences of a prescribed size</a>, arXiv:2504.03013 [math.CO], 2025. See p. 6.
%F A277666 G.f. of column k: 1/(1 + Sum_{j=1..k} (k+1-j)*(-x)^j).
%e A277666 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}).
%e A277666 Square array A(n,k) begins:
%e A277666   1, 1, 1,   1,    1,     1,      1,      1, ...
%e A277666   0, 1, 2,   3,    4,     5,      6,      7, ...
%e A277666   0, 1, 3,   7,   13,    21,     31,     43, ...
%e A277666   0, 1, 4,  16,   42,    88,    160,    264, ...
%e A277666   0, 1, 5,  37,  136,   369,    826,   1621, ...
%e A277666   0, 1, 6,  86,  440,  1547,   4264,   9953, ...
%e A277666   0, 1, 7, 200, 1423,  6486,  22012,  61112, ...
%e A277666   0, 1, 8, 465, 4602, 27194, 113632, 375231, ...
%p A277666 A:= proc(n, k) option remember; `if`(n<0, 0, `if`(n=0, 1,
%p A277666       -add((-1)^j*(k+1-j)*A(n-j, k), j=1..k)))
%p A277666     end:
%p A277666 seq(seq(A(n, d-n), n=0..d), d=0..14);
%t A277666 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}]]];
%t A277666 Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* _Jean-François Alcover_, Jun 08 2018, from Maple *)
%Y A277666 Columns k=0-10 give: A000007, A000012, A000027(n+1), A095263(n+1), A277667, A277668, A277669, A277670, A277671, A277672, A096261.
%Y A277666 Rows n=0-2 give: A000012, A001477, A002061 (for k>0).
%Y A277666 Main diagonal gives A277673.
%K A277666 nonn,tabl
%O A277666 0,8
%A A277666 _Alois P. Heinz_, Oct 26 2016