login
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

%I #21 Sep 08 2022 08:45:13

%S 1,0,2,0,1,5,0,4,6,14,0,20,30,28,42,0,120,180,168,120,132,0,840,1260,

%T 1176,840,495,429,0,6720,10080,9408,6720,3960,2002,1430,0,60480,90720,

%U 84672,60480,35640,18018,8008,4862,0,604800,907200,846720,604800,356400,180180,80080,31824,16796

%N 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.

%C Row sums are the factorial numbers (A000142).

%C Diagonal is A000108.

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

%H G. C. Greubel, <a href="/A092583/b092583.txt">Rows n = 1..100 of triangle, flattened</a>

%H E. Deutsch and W. P. Johnson, <a href="http://www.jstor.org/stable/3219101">Create your own permutation statistics</a>, Math. Mag., 77, 130-134, 2004.

%H R. Simion and F. W. Schmidt, <a href="https://doi.org/10.1016/S0195-6698(85)80052-4">Restricted permutations</a>, European J. Combin., 6, 383-406, 1985.

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

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

%e 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).

%e Triangle starts:

%e 1;

%e 0, 2;

%e 0, 1, 5;

%e 0, 4, 6, 14;

%e 0, 20, 30, 28, 42;

%e 0, 120, 180, 168, 120, 132;

%e 0, 840, 1260, 1176, 840, 495, 429;

%e ...

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

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

%o (Magma)

%o T:= func< n,k | k eq n select Catalan(n) else Factorial(n)*Binomial(2*k, k-2)/Factorial(k+1) >;

%o [T(n,k): k in [1..n], n in [1..12]]; // _G. C. Greubel_, Jul 22 2019

%o (Sage)

%o def T(n, k):

%o if (k==n): return catalan_number(n)

%o else: return factorial(n)*binomial(2*k, k-2)/factorial(k+1)

%o [[T(n,k) for k in (1..n)] for n in (1..12)] # _G. C. Greubel_, Jul 22 2019

%o (GAP)

%o T:= function(n,k)

%o if k=n then return Binomial(2*n, n)/(n + 1);

%o else return Factorial(n)*Binomial(2*k, k-2)/Factorial(k+1);

%o fi;

%o end;

%o Flat(List([1..12], n-> List([1..n], k-> T(n,k) ))); # _G. C. Greubel_, Jul 22 2019

%Y Cf. A000142, A000108, A002694.

%K nonn,tabl

%O 1,3

%A _Emeric Deutsch_ and Warren P. Johnson (wjohnson(AT)bates.edu), Apr 10 2004