|
| |
|
|
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.
|
|
0
| |
|
|
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
(list; table; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Row sums are the factorial numbers (A000142). Diagonal is A000139.
|
|
|
REFERENCES
| E. Deutsch and W. P. Johnson, Create your own permutation statistics, Math. Mag., 77, 130-134, 2004.
R. P. Stanley, Enumerative Combinatorics, Vol. 2, Cambridge Univ. Press, Cambridge, 1999, pp. 241, 275.
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(4k+3)n!binomial(3k-1, k-3)/[(2k+3)(k+2)! ] for k<n; T(n, n)=2(3n)!/[(2n+1)!(n+1)! ].
|
|
|
EXAMPLE
| 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.
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: A132710 A106512 A181229 * A035536 A205974 A098643
Adjacent sequences: A094782 A094783 A094784 * A094786 A094787 A094788
|
|
|
KEYWORD
| nonn,tabl
|
|
|
AUTHOR
| Emeric Deutsch and Warren P. Johnson (deutsch(AT)duke.poly.edu), Jun 10 2004
|
| |
|
|
