%I #15 Aug 28 2024 09:36:50
%S 1,0,2,0,0,6,0,0,2,22,0,0,10,19,91,0,0,60,114,138,408,0,0,420,798,966,
%T 918,1938,0,0,3360,6384,7728,7344,5890,9614,0,0,30240,57456,69552,
%U 66096,53010,37191,49335,0,0,302400,574560,695520,660960,530100,371910,233220
%N Triangle read by rows: T(n,k) is the number of permutations p of [n] such that the length of the longest 2-stack sortable initial segment of p is equal to k.
%C Row sums are the factorial numbers (A000142). Diagonal is A000139.
%D R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, pp. 241, 275.
%H Emeric Deutsch and Warren P. Johnson, <a href="http://www.jstor.org/stable/3219101">Create your own permutation statistics</a>, Math. Mag., 77, 130-134, 2004.
%H J. West, <a href="http://dx.doi.org/10.1016/0304-3975(93)90321-J">Sorting twice through a stack</a>, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991). Theoret. Comput. Sci. 117 (1993), no. 1-2, 303-313.
%F T(n, k) = 6*(4*k+3)*n!*binomial(3*k-1, k-3)/((2*k+3)*(k+2)!) for k<n; T(n, n)=2*(3*n)!/((2*n+1)!*(n+1)!).
%e T(4,3)=2 because 2341 and 3241 are the only permutations of [4] which are not 2-stack sortable but their initial segments of length 3 (i.e. 234 and 324) are 2-stack sortable.
%e Triangle begins:
%e 1;
%e 0, 2;
%e 0, 0, 6;
%e 0, 0, 2, 22;
%e 0, 0, 10, 19, 91;
%e 0, 0, 60, 114, 138, 408;
%e ...
%p T:=proc(n,k) if k<n then 6*(4*k+3)*n!*binomial(3*k-1,k-3)/(2*k+3)/(k+2)! elif k=n then 2*(3*n)!/(2*n+1)!/(n+1)! else 0 fi end: seq(seq(T(n,k),k=1..n), n=1..12);
%Y Cf. A000142, A000139.
%K nonn,tabl
%O 1,3
%A _Emeric Deutsch_ and Warren P. Johnson, Jun 10 2004