OFFSET
0,12
COMMENTS
The first and the last letters are considered neighbors in a cyclic alphabet. The words are not considered cyclic here.
A(n,k) is also the number of (n*k-1)-step walks on k-dimensional cubic lattice from (1,0,...,0) to (n,n,...,n) with positive unit steps in all dimensions such that the indices of dimensions used in consecutive steps differ by less than 2 or are in the set {1,k}.
EXAMPLE
A(0,0) = A(n,0) = A(0,k) = 1: the empty word.
A(1,2) = 1 = |{ab}|.
A(1,3) = 2 = |{abc, acb}|.
A(1,4) = 2 = |{abcd, adcb}|.
A(2,2) = 3 = |{aabb, abab, abba}|.
A(2,4) = 62 = |{aabbccdd, aabbcdcd, aabbcddc, aabcbcdd, aabcddcb, aadcbbcd, aadcdcbb, aaddcbbc, aaddcbcb, aaddccbb, ababccdd, ababcdcd, ababcddc, abadcbcd, abadcdcb, abaddcbc, abaddccb, abbadccd, abbadcdc, abbaddcc, abbccdad, abbccdda, abbcdadc, abbcdcda, abcbadcd, abcbaddc, abcbcdad, abcbcdda, abccbadd, abccddab, abcdabcd, abcdadcb, abcdcbad, abcdcdab, abcddabc, abcddcba, adabbccd, adabbcdc, adabcbcd, adabcdcb, adadcbbc, adadcbcb, adadccbb, adcbabcd, adcbadcb, adcbbadc, adcbbcda, adcbcbad, adcbcdab, adccbbad, adccdabb, adcdabbc, adcdabcb, adcdcbab, adcdcbba, addabbcc, addabcbc, addabccb, addcbabc, addcbcba, addccbab, addccbba}|.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
1, 1, 1, 2, 2, 2, 2, ...
1, 1, 3, 30, 62, 114, 202, ...
1, 1, 10, 560, 2830, 12622, 53768, ...
1, 1, 35, 11550, 151686, 1754954, 19341130, ...
1, 1, 126, 252252, 8893482, 276049002, 8151741752, ...
1, 1, 462, 5717712, 552309938, 46957069166, 3795394507240, ...
MAPLE
b:= proc() option remember; local n; n:= nargs;
`if`(n<2 or {0}={args}, 1,
`if`(n=2, `if`(args[1]>0, b(args[1]-1, args[2]), 0)+
`if`(args[2]>0, b(args[2]-1, args[1]), 0),
`if`(args[1]>0, b(args[1]-1, seq(args[i], i=2..n)), 0)+
`if`(args[2]>0, b(args[2]-1, seq(args[i], i=3..n), args[1]), 0)+
`if`(args[n]>0, b(args[n]-1, seq(args[i], i=1..n-1)), 0)))
end:
A:= (n, k)-> `if`(n=0 or k=0, 1, b(n-1, n$(k-1))):
seq(seq(A(n, d-n), n=0..d), d=0..9);
MATHEMATICA
b[args__] := b[args] = With[{n = Length[{args}]}, If[n<2 || {0} == Union[ {args}], 1, If[n==2, If[{args}[[1]]>0, b[{args}[[1]]-1, {args}[[2]] ], 0] + If[{args}[[2]]>0, b[{args}[[2]]-1, {args}[[1]] ], 0], If[{args}[[1]]>0, b[{args}[[1]]-1, Sequence @@ {args}[[2;; n]] ], 0] + If[{args}[[2]]>0, b[{args}[[2]]-1, Sequence @@ {args}[[3;; n]], {args}[[1]] ], 0]+ If[{args}[[n]]>0, b[{args}[[n]]-1, Sequence @@ Most[{args}]] ], 0]] /. Null -> 0];
a[n_, k_]:= If[n==0 || k==0, 1, b[n-1, Sequence @@ Array[n&, k-1]]];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 9}] // Flatten (* Jean-François Alcover, Dec 13 2013, translated from Maple *)
CROSSREFS
KEYWORD
AUTHOR
Alois P. Heinz, Mar 02 2012
STATUS
approved