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
KEYWORD
nonn,tabl
AUTHOR
Ralf Stephan, Apr 20 2004
STATUS
approved