|
| |
|
|
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.
|
|
6
|
|
|
|
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
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
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
|
|
|
|
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
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
