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,3

Comments

Row sums are the factorial numbers (A000142).

Diagonal is A000108.

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

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.

Formula

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

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

Example

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

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

Prog

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

Crossrefs

Cf. A000142, A000108, A002694.

Sequence in context: A325304 A134433 A125183 * A321619 A285212 A262948

Adjacent sequences: A092580 A092581 A092582 * A092584 A092585 A092586

Keyword

nonn,tabl

Author

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

Status

approved