A094785 - OEIS

%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