OFFSET
1,3
COMMENTS
A(n,k) is the number of n-long k-ary words that simultaneously avoid the patterns 112 and 221.
LINKS
G. C. Greubel, Antidiagonals n = 1..50, flattened
A. Burstein and T. Mansour, Words restricted by patterns with at most 2 distinct letters, arXiv:math/0110056 [math.CO], 2001.
FORMULA
A(n, k) = k!*binomial(n, k) + Sum_{j=1..k-1} j*j!*binomial(n, j), for 2 <= k <= n, otherwise Sum_{j=1..n} j*j!*binomial(n, j), with A(1, k) = 1 and A(n, 1) = n.
From G. C. Greubel, Dec 29 2021: (Start)
T(n, k) = A(k, n-k+1).
Sum_{k=1..n} T(n, k) = A093963(n).
T(n, 1) = 1.
T(n, n) = n.
T(n, n-1) = (n-1)^2.
T(n, n-2) = A069778(n).
T(2*n-1, n) = A093965(n).
T(2*n, n) = A093964(n), for n >= 1. (End)
EXAMPLE
Array, A(n, k), begins as:
1, 1, 1, 1, 1, 1, 1 ... 1*A000012(k);
2, 4, 6, 6, 6, 6, 6 ... 2*A158799(k-1);
3, 9, 21, 33, 33, 33, 33 ... ;
4, 16, 52, 124, 196, 196, 196 ... ;
5, 25, 105, 345, 825, 1305, 1305 ... ;
6, 36, 186, 786, 2586, 6186, 9786 ... ;
7, 49, 301, 1561, 6601, 21721, 51961 ... ;
Antidiagonal triangle, T(n, k), begins as:
1;
1, 2;
1, 4, 3;
1, 6, 9, 4;
1, 6, 21, 16, 5;
1, 6, 33, 52, 25, 6;
1, 6, 33, 124, 105, 36, 7;
1, 6, 33, 196, 345, 186, 49, 8;
1, 6, 33, 196, 825, 786, 301, 64, 9;
1, 6, 33, 196, 1305, 2586, 1561, 456, 81, 10;
MATHEMATICA
A[n_, k_]:= A[n, k]= If[n==1, 1, If[k==1, n, If[2<=k<n+1, (1-k)*k!*Binomial[n, k] + Sum[j*j!*Binomial[n, j], {j, k}], Sum[j*j!*Binomial[n, j], {j, n}] ]]];
T[n_, k_]:= A[k, n-k+1];
Table[T[k, k], {n, 15}, {k, n}]//Flatten (* G. C. Greubel, Dec 29 2021 *)
PROG
(PARI) A(n, k) = if(n >= k+1, sum(j=1, k, j*j!*binomial(k, j)), if(n<2, if(n<1, 0, k), n!*binomial(k, n) + sum(j=1, n-1, j*j!*binomial(k, j))));
T(n, k) = A(n-k+1, k);
for(n=1, 15, for(k=1, n, print1(T(n, k), ", ") ) )
(Sage)
@CachedFunction
def A(n, k):
if (n==1): return 1
elif (k==1): return n
elif (2 <= k < n+1): return factorial(k)*binomial(n, k) + sum( j*factorial(j)*binomial(n, j) for j in (1..k-1) )
else: return sum( j*factorial(j)*binomial(n, j) for j in (1..n) )
def T(n, k): return A(k, n-k+1)
flatten([[T(n, k) for k in (1..n)] for n in (1..15)]) # G. C. Greubel, Dec 29 2021
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Apr 20 2004
STATUS
approved