A093190 Array t read by antidiagonals: number of {112,212}-avoiding words.

1, 1, 2, 1, 4, 3, 1, 6, 9, 4, 1, 8, 21, 16, 5, 1, 10, 39, 52, 25, 6, 1, 12, 63, 136, 105, 36, 7, 1, 14, 93, 292, 365, 186, 49, 8, 1, 16, 129, 544, 1045, 816, 301, 64, 9, 1, 18, 171, 916, 2505, 3006, 1603, 456, 81, 10, 1, 20, 219, 1432, 5225, 9276, 7315, 2864, 657, 100, 11

Offset

1,3

Comments

t(k,n) = number of n-long k-ary words that simultaneously avoid the patterns 112 and 212.

Links

G. C. Greubel, Antidiagonal rows 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

t(n, k) = Sum{j=0..n} j!*C(n, j)*C(k-1, j-1). (square array)

T(n, k) = Sum_{j=0..n-k+1} j!*binomial(k,j)*binomial(n-k,j-1). (number triangle) - G. C. Greubel, Mar 09 2021

Example

Square array begins as:
  1  1   1   1    1    1 ... 1*A000012;
  2  4   6   8   10   12 ... 2*A000027;
  3  9  21  39   63   93 ... 3*A002061;
  4 16  52 136  292  544 ... 4*A135859;
  5 25 105 365 1045 2505 ... ;
Antidiagonal rows begins as:
  1;
  1,  2;
  1,  4,  3;
  1,  6,  9,   4;
  1,  8, 21,  16,   5;
  1, 10, 39,  52,  25,  6;
  1, 12, 63, 136, 105, 36, 7;

Mathematica

T[n_, k_]:= Sum[j!*Binomial[k, j]*Binomial[n-k, j-1], {j, 0, n-k+1}];
Table[T[n, k], {n, 12}, {k, n}]//Flatten (* G. C. Greubel, Mar 09 2021 *)

Prog

(PARI) t(n, k)=sum(j=0, k, j!*binomial(k, j)*binomial(n-1, j-1))
(Sage) flatten([[ sum(factorial(j)*binomial(k, j)*binomial(n-k, j-1) for j in (0..n-k+1)) for k in (1..n)] for n in (1..12)]) # G. C. Greubel, Mar 09 2021
(Magma) [(&+[Factorial(j)*Binomial(k, j)*Binomial(n-k, j-1): j in [0..n-k+1]]): k in [1..n], n in [1..12]]; // G. C. Greubel, Mar 09 2021

Crossrefs

Main diagonal is A052852.

Antidiagonal sums are in A084261 - 1.

Sequence in context: A103406 A142978 A152060 * A132191 A094437 A172431

Adjacent sequences: A093187 A093188 A093189 * A093191 A093192 A093193

Keyword

nonn,tabl

Author

Ralf Stephan, Apr 20 2004

Status

approved