A208879 Number of words A(n,k), either empty or beginning with the first letter of the cyclic k-ary alphabet, where each letter of the alphabet occurs n times and letters of neighboring word positions are equal or neighbors in the alphabet; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 3, 1, 1, 1, 2, 30, 10, 1, 1, 1, 2, 62, 560, 35, 1, 1, 1, 2, 114, 2830, 11550, 126, 1, 1, 1, 2, 202, 12622, 151686, 252252, 462, 1, 1, 1, 2, 346, 53768, 1754954, 8893482, 5717712, 1716, 1, 1

Offset: 0

Author

Alois P. Heinz, Mar 02 2012

Keywords

• nonn
• tabl
• walk

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}.

Examples

			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, ...
		

Crossrefs

Columns k=0+1, 2-6 give: A000012, A088218, A208881, A209183, A209184, A209185.

Rows n=0, 2 give: A000012, A208880.

Cf. A208673 (noncyclic alphabet).

Programs

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 *)