A092583 Triangle read by rows: T(n,k) is the number of permutations p of [n] in which the length of the longest initial segment avoiding the 123-pattern is equal to k.

1, 0, 2, 0, 1, 5, 0, 4, 6, 14, 0, 20, 30, 28, 42, 0, 120, 180, 168, 120, 132, 0, 840, 1260, 1176, 840, 495, 429, 0, 6720, 10080, 9408, 6720, 3960, 2002, 1430, 0, 60480, 90720, 84672, 60480, 35640, 18018, 8008, 4862, 0, 604800, 907200, 846720, 604800, 356400, 180180, 80080, 31824, 16796

Offset: 1

Author

Emeric Deutsch and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004

Keywords

• nonn
• tabl

Comments

Row sums are the factorial numbers (A000142).

Diagonal is A000108.

T(n,n-1) = binomial(2n-2,n-3) = A002694(n-1).

Examples

			T(4,3) = 6 because 1324, 1423, 2134, 2314, 3124 and 4123 are the only permutations of [4] in which the length of the longest initial segment avoiding the 123-pattern is equal to 3 (i.e., the first three entries do not contain the 123-pattern but all 4 of them do).
Triangle starts:
  1;
  0,    2;
  0,    1,    5;
  0,    4,    6,   14;
  0,   20,   30,   28,   42;
  0,  120,  180,  168,  120,  132;
  0,  840, 1260, 1176,  840,  495,  429;
  ...
		

Links

• G. C. Greubel, Rows n = 1..100 of triangle, flattened
• E. Deutsch and W. P. Johnson, Create your own permutation statistics, Math. Mag., 77, 130-134, 2004.
• R. Simion and F. W. Schmidt, Restricted permutations, European J. Combin., 6, 383-406, 1985.

Crossrefs

Cf. A000142, A000108, A002694.

Programs

GAP

T:= function(n,k)
    if k=n then return Binomial(2*n, n)/(n + 1);
    else return Factorial(n)*Binomial(2*k, k-2)/Factorial(k+1);
    fi;
  end;
Flat(List([1..12], n-> List([1..n], k-> T(n,k) ))); # G. C. Greubel, Jul 22 2019

Magma

T:= func< n,k | k eq n select Catalan(n) else Factorial(n)*Binomial(2*k, k-2)/Factorial(k+1) >;
[T(n,k): k in [1..n], n in [1..12]]; // G. C. Greubel, Jul 22 2019

Mathematica

T[n_,k_]:= If[k==n, CatalanNumber[n], n!*Binomial[2*k,k-2]/(k+1)!]; Table[T[n,k], {n,12}, {k,n}]//Flatten (* G. C. Greubel, Jul 22 2019 *)

PARI

tabl(nn) = {for (n=1, nn, for (k=1, n-1, print1(n!*binomial(2*k, k-2)/(k+1)!, ", ");); print1(binomial(2*n, n)/(n+1), ", "); print(););} \\ Michel Marcus, Jul 16 2013

Sage

def T(n, k):
    if (k==n): return catalan_number(n)
    else: return factorial(n)*binomial(2*k, k-2)/factorial(k+1)
[[T(n,k) for k in (1..n)] for n in (1..12)] # G. C. Greubel, Jul 22 2019

Formula

T(n,k) = n!*binomial(2k, k-2)/(k+1)! for k < n;

T(n,n) = binomial(2n, n)/(n+1) = A000108(n).