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

Links

Table of n, a(n) for n=0..54.

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

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

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

Cf. A208673 (noncyclic alphabet).

Sequence in context: A211984 A275471 A094006 * A179617 A140188 A180050

Adjacent sequences: A208876 A208877 A208878 * A208880 A208881 A208882

Keyword

nonn,tabl,walk

Author

Alois P. Heinz, Mar 02 2012

Status

approved