proposed

approved

editing

proposed

Array read by antidiagonals: number of {112,221}-avoiding words.

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

proposed

editing

editing

proposed

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

proposed

editing

editing

proposed

Array , A(n, k), begins as:

Antiriagonal Antidiagonal triangle , T(n, k), begins as:

Array T read by antidiagonals: {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, 1, 6, 33

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

G. C. Greubel, <a href="/A093966/b093966.txt">Antidiagonals n = 1..50, flattened</a>

For A(n>=, k+1, T() = k, !*binomial(n) = sum{, k) + Sum_{j=1..n, k-1} j*kj!*Cbinomial(n, k)} = A093964(kj); , for 2<=n <=k, T( k, n) <= n!*C(k, n)+sum, otherwise Sum_{kj=1..n, k} j*kj!*Cbinomial(n, kj)}; T, with A(1, k, 0) = 1, T and A(k, n, 1) =k 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)

Array 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 ... ;

Antiriagonal triangle 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;

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 *)

(PARI) TA(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

Main diagonal is A093965, antidiagonal sums are in A093963.

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

approved

editing

editing

approved

_Ralf Stephan, _, Apr 20 2004

proposed

editing