A093966 Array read by antidiagonals: number of {112,221}-avoiding words.
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, 1, 6, 33, 196, 1305, 6186, 6601, 2808, 657, 100, 11
Offset: 1
Examples
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;
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.
Programs
-
Mathematica
A[n_, k_]:= A[n, k]= If[n==1, 1, If[k==1, n, If[2<=k
-
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
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)
Comments