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,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

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

Sequence in context: A179000 A210559 A180803 * A103406 A142978 A152060

Adjacent sequences: A093963 A093964 A093965 * A093967 A093968 A093969

Keyword

nonn,tabl

Author

Ralf Stephan, Apr 20 2004

Status

approved