login
A220062
Number A(n,k) of n length words over k-ary alphabet, where neighboring letters are neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.
13
1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 3, 2, 0, 0, 1, 4, 4, 2, 0, 0, 1, 5, 6, 6, 2, 0, 0, 1, 6, 8, 10, 8, 2, 0, 0, 1, 7, 10, 14, 16, 12, 2, 0, 0, 1, 8, 12, 18, 24, 26, 16, 2, 0, 0, 1, 9, 14, 22, 32, 42, 42, 24, 2, 0, 0, 1, 10, 16, 26, 40, 58, 72, 68, 32, 2, 0, 0
OFFSET
0,8
COMMENTS
Equivalently, the number of walks of length n-1 on the path graph P_k. - Andrew Howroyd, Apr 17 2017
LINKS
EXAMPLE
A(5,3) = 12: there are 12 words of length 5 over 3-ary alphabet {a,b,c}, where neighboring letters are neighbors in the alphabet: ababa, ababc, abcba, abcbc, babab, babcb, bcbab, bcbcb, cbaba, cbabc, cbcba, cbcbc.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 2, 3, 4, 5, 6, 7, ...
0, 0, 2, 4, 6, 8, 10, 12, ...
0, 0, 2, 6, 10, 14, 18, 22, ...
0, 0, 2, 8, 16, 24, 32, 40, ...
0, 0, 2, 12, 26, 42, 58, 74, ...
0, 0, 2, 16, 42, 72, 104, 136, ...
0, 0, 2, 24, 68, 126, 188, 252, ...
MAPLE
b:= proc(n, i, k) option remember; `if`(n=0, 1,
`if`(i=0, add(b(n-1, j, k), j=1..k),
`if`(i>1, b(n-1, i-1, k), 0)+
`if`(i<k, b(n-1, i+1, k), 0)))
end:
A:= (n, k)-> b(n, 0, k):
seq(seq(A(n, d-n), n=0..d), d=0..14);
MATHEMATICA
b[n_, i_, k_] := b[n, i, k] = If[n == 0, 1, If[i == 0, Sum[b[n-1, j, k], {j, 1, k}], If[i>1, b[n-1, i-1, k], 0] + If[i<k, b[n-1, i+1, k], 0]]]; A[n_, k_] := b[n, 0, k]; Table[Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 19 2015, after Alois P. Heinz *)
PROG
(PARI)
TransferGf(m, u, t, v, z)=vector(m, i, u(i))*matsolve(matid(m)-z*matrix(m, m, i, j, t(i, j)), vectorv(m, i, v(i)));
ColGf(m, z)=1+z*TransferGf(m, i->1, (i, j)->abs(i-j)==1, j->1, z);
a(n, k)=Vec(ColGf(k, x) + O(x^(n+1)))[n+1];
for(n=0, 7, for(k=0, 7, print1( a(n, k), ", ") ); print(); );
\\ Andrew Howroyd, Apr 17 2017
CROSSREFS
Columns k=0, 2-10 give: A000007, A040000, A029744(n+2) for n>0, A006355(n+3) for n>0, A090993(n+1) for n>0, A090995(n-1) for n>2, A129639, A153340, A153362, A153360.
Rows 0-6 give: A000012, A001477, A005843(k-1) for k>0, A016825(k-2) for k>1, A008590(k-2) for k>2, A113770(k-2) for k>3, A063164(k-2) for k>4.
Main diagonal gives: A102699.
Sequence in context: A292377 A216238 A157608 * A216054 A217257 A217315
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Dec 03 2012
STATUS
approved