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
Alois P. Heinz, Rows n = 0..140, flattened
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.
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Dec 03 2012
STATUS
approved