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

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, 918, 1938, 0, 0, 3360, 6384, 7728, 7344, 5890, 9614, 0, 0, 30240, 57456, 69552, 66096, 53010, 37191, 49335, 0, 0, 302400, 574560, 695520, 660960, 530100, 371910, 233220

Offset

1,3

Comments

Row sums are the factorial numbers (A000142). Diagonal is A000139.

References

R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, pp. 241, 275.

Links

Table of n, a(n) for n=1..54.

Emeric Deutsch and Warren P. Johnson, Create your own permutation statistics, Math. Mag., 77, 130-134, 2004.

J. West, Sorting twice through a stack, Conference on Formal Power Series and Algebraic Combinatorics (Bordeaux, 1991). Theoret. Comput. Sci. 117 (1993), no. 1-2, 303-313.

Formula

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)!).

Example

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.
Triangle begins:
  1;
  0, 2;
  0, 0, 6;
  0, 0, 2, 22;
  0, 0, 10, 19, 91;
  0, 0, 60, 114, 138, 408;
  ...

Maple

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

Crossrefs

Cf. A000142, A000139.

Sequence in context: A364230 A259857 A364790 * A265856 A035536 A205974

Adjacent sequences: A094782 A094783 A094784 * A094786 A094787 A094788

Keyword

nonn,tabl

Author

Emeric Deutsch and Warren P. Johnson, Jun 10 2004

Status

approved