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

%I #13 Dec 29 2021 09:53:55

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

%T 1,14,93,292,365,186,49,8,1,16,129,544,1045,816,301,64,9,1,18,171,916,

%U 2505,3006,1603,456,81,10,1,20,219,1432,5225,9276,7315,2864,657,100,11

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

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

%H G. C. Greubel, <a href="/A093190/b093190.txt">Antidiagonal rows n = 1..50, flattened</a>

%H A. Burstein and T. Mansour, <a href="https://arxiv.org/abs/math/0110056">Words restricted by patterns with at most 2 distinct letters</a>, arXiv:math/0110056 [math.CO], 2001.

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

%F 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

%e Square array begins as:

%e 1 1 1 1 1 1 ... 1*A000012;

%e 2 4 6 8 10 12 ... 2*A000027;

%e 3 9 21 39 63 93 ... 3*A002061;

%e 4 16 52 136 292 544 ... 4*A135859;

%e 5 25 105 365 1045 2505 ... ;

%e Antidiagonal rows begins as:

%e 1;

%e 1, 2;

%e 1, 4, 3;

%e 1, 6, 9, 4;

%e 1, 8, 21, 16, 5;

%e 1, 10, 39, 52, 25, 6;

%e 1, 12, 63, 136, 105, 36, 7;

%t T[n_, k_]:= Sum[j!*Binomial[k, j]*Binomial[n-k, j-1], {j,0,n-k+1}];

%t Table[T[n, k], {n,12}, {k,n}]//Flatten (* _G. C. Greubel_, Mar 09 2021 *)

%o (PARI) t(n,k)=sum(j=0,k,j!*binomial(k,j)*binomial(n-1,j-1))

%o (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

%o (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

%Y Main diagonal is A052852.

%Y Antidiagonal sums are in A084261 - 1.

%K nonn,tabl

%O 1,3

%A _Ralf Stephan_, Apr 20 2004