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
Examples
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, ..
Links
- Andrew Howroyd, Table of n, a(n) for n = 0..1325
Crossrefs
Programs
-
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`(t0, 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 *) -
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
Comments