|
%I #29 Feb 02 2019 15:50:14
%S 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,
%T 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,
%U 42,24,2,0,0,1,10,16,26,40,58,72,68,32,2,0,0
%N 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.
%C Equivalently, the number of walks of length n-1 on the path graph P_k. - _Andrew Howroyd_, Apr 17 2017
%H Alois P. Heinz, <a href="/A220062/b220062.txt">Rows n = 0..140, flattened</a>
%e 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.
%e Square array A(n,k) begins:
%e 1, 1, 1, 1, 1, 1, 1, 1, ...
%e 0, 1, 2, 3, 4, 5, 6, 7, ...
%e 0, 0, 2, 4, 6, 8, 10, 12, ...
%e 0, 0, 2, 6, 10, 14, 18, 22, ...
%e 0, 0, 2, 8, 16, 24, 32, 40, ...
%e 0, 0, 2, 12, 26, 42, 58, 74, ...
%e 0, 0, 2, 16, 42, 72, 104, 136, ...
%e 0, 0, 2, 24, 68, 126, 188, 252, ...
%p b:= proc(n, i, k) option remember; `if`(n=0, 1,
%p `if`(i=0, add(b(n-1, j, k), j=1..k),
%p `if`(i>1, b(n-1, i-1, k), 0)+
%p `if`(i<k, b(n-1, i+1, k), 0)))
%p end:
%p A:= (n, k)-> b(n, 0, k):
%p seq(seq(A(n, d-n), n=0..d), d=0..14);
%t 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_ *)
%o (PARI)
%o 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)));
%o ColGf(m,z)=1+z*TransferGf(m, i->1, (i,j)->abs(i-j)==1, j->1, z);
%o a(n,k)=Vec(ColGf(k,x) + O(x^(n+1)))[n+1];
%o for(n=0, 7, for(k=0, 7, print1( a(n,k), ", ") ); print(); );
%o \\ _Andrew Howroyd_, Apr 17 2017
%Y 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.
%Y 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.
%Y Main diagonal gives: A102699.
%Y Cf. A198632, A188866, A276562, A208727, A208671.
%K nonn,tabl
%O 0,8
%A _Alois P. Heinz_, Dec 03 2012
|
