A208673 Number of words A(n,k), either empty or beginning with the first letter of the 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, 1, 3, 1, 1, 1, 1, 5, 10, 1, 1, 1, 1, 9, 37, 35, 1, 1, 1, 1, 15, 163, 309, 126, 1, 1, 1, 1, 25, 640, 3593, 2751, 462, 1, 1, 1, 1, 41, 2503, 36095, 87501, 25493, 1716, 1, 1, 1, 1, 67, 9559, 362617, 2336376, 2266155, 242845, 6435, 1, 1

Offset

0,13

Comments

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 absolute difference of the dimension indices used in consecutive steps is <= 1.

All rows are linear recurrences with constant coefficients and for n > 0 the order of the recurrence is bounded by 2*n-1. For n up to at least 20 this upper bound is exact. - Andrew Howroyd, Feb 22 2022

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1325

Example

A(0,0) = A(n,0) = A(0,k) = 1: the empty word.
A(2,3) = 5:
  +------+   +------+   +------+   +------+   +------+
  |aabbcc|   |aabcbc|   |aabccb|   |ababcc|   |abccba|
  +------+   +------+   +------+   +------+   +------+
  |122222|   |122222|   |122222|   |112222|   |111112|
  |001222|   |001122|   |001112|   |011222|   |011122|
  |000012|   |000112|   |000122|   |000012|   |001222|
  +------+   +------+   +------+   +------+   +------+
  |xx    |   |xx    |   |xx    |   |x x   |   |x    x|
  |  xx  |   |  x x |   |  x  x|   | x x  |   | x  x |
  |    xx|   |   x x|   |   xx |   |    xx|   |  xx  |
  +------+   +------+   +------+   +------+   +------+
Square array A(n,k) begins:
  1,  1,    1,     1,       1,         1,           1, ..
  1,  1,    1,     1,       1,         1,           1, ..
  1,  1,    3,     5,       9,        15,          25, ..
  1,  1,   10,    37,     163,       640,        2503, ..
  1,  1,   35,   309,    3593,     36095,      362617, ..
  1,  1,  126,  2751,   87501,   2336376,    62748001, ..
  1,  1,  462, 25493, 2266155, 164478048, 12085125703, ..

Maple

b:= proc(t, l) option remember; local n; n:= nops(l);
     `if`(n<2 or {0}={l[]}, 1,
     `if`(l[t]>0, b(t, [seq(l[i]-`if`(i=t, 1, 0), i=1..n)]), 0)+
     `if`(t<n and l[t+1]>0,
                  b(t+1, [seq(l[i]-`if`(i=t+1, 1, 0), i=1..n)]), 0)+
     `if`(t>1 and l[t-1]>0,
                  b(t-1, [seq(l[i]-`if`(i=t-1, 1, 0), i=1..n)]), 0))
    end:
A:= (n, k)-> `if`(n=0 or k=0, 1, b(1, [n-1, n$(k-1)])):
seq(seq(A(n, d-n), n=0..d), d=0..10);

Mathematica

b[t_, l_List] := b[t, l] = Module[{n = Length[l]}, If[n < 2 || {0} == Union[l], 1, If[l[[t]] > 0, b[t, Table[l[[i]] - If[i == t, 1, 0], {i, 1, n}]], 0] + If[t < n && l[[t + 1]] > 0, b[t + 1, Table[l[[i]] - If[i == t + 1, 1, 0], {i, 1, n}]], 0] + If[t > 1 && l[[t - 1]] > 0, b[t - 1, Table[l[[i]] - If[i == t - 1, 1, 0], {i, 1, n}]], 0]]]; A[n_, k_] := If[n == 0 || k == 0, 1, b[1, Join[{n - 1}, Array[n&, k - 1]]]]; Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 10}] // Flatten (* Jean-François Alcover, Dec 27 2013, translated from Maple *)

Prog

(PARI)
F(u)={my(n=#u); sum(k=1, n, u[k]*binomial(n-1, k-1))}
step(u, c)={my(n=#u); vector(n, k, sum(i=max(0, 2*k-c-n), k-1, sum(j=0, n-2*k+i+c, u[k-i+j]*binomial(n-1, 2*k-1-c-i+j)*binomial(k-1, k-i-1)*binomial(k-i+j-c, j) ))) }
R(n, k)={my(r=vector(n+1), u=vector(k), v=vector(k)); u[1]=v[1]=r[1]=r[2]=1; for(n=3, #r, u=step(u, 1); v=step(v, 0)+u; r[n]=F(v)); r}
T(n, k)={if(n==0||k==0, 1, R(k, n)[1+k])} \\ Andrew Howroyd, Feb 22 2022

Crossrefs

Columns k=0+1, 2-4 give: A000012, A088218, A208675, A212334.

Rows n=0+1, 2-3 give: A000012, A001595, A208674.

Main diagonal gives A351759.

Cf. A208879 (cyclic alphabet), A331562.

Sequence in context: A111368 A140750 A028264 * A010122 A220693 A208615

Adjacent sequences: A208670 A208671 A208672 * A208674 A208675 A208676

Keyword

nonn,tabl

Author

Alois P. Heinz, Feb 29 2012

Status

approved