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

Author

Ralf Stephan, Apr 20 2004

Keywords

• nonn
• tabl

Comments

A(n,k) is the number of n-long k-ary words that simultaneously avoid the patterns 112 and 221.

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.

Crossrefs

Cf. A069778, A093963 (antidiagonal sums), A093964, A093965 (main diagonal).

Programs

Mathematica

A[n_, k_]:= A[n, k]= If[n==1, 1, If[k==1, n, If[2<=kG. C. Greubel, Dec 29 2021 *)

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)