|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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(); );
|
|
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.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|