A027361 Number of "sorted permutations": permutations that can occur as the output of the sorting procedure described by Knuth.

1, 1, 1, 2, 5, 17, 68, 326, 1780, 11033, 76028, 578290, 4803696, 43297358, 420639362, 4382320595, 48729809104, 576039659209, 7213070102518, 95373808983223, 1327842798808220, 19416307366048221, 297499363267839558, 4766432683120731044, 79699553284422816437, 1388383661114307067780, 25156549558328842669336

Offset

0,4

References

D. E. Knuth, The Art of Computer Programming Vol. 1, p. 238.

Links

Table of n, a(n) for n=0..26.

M. Bousquet-Mélou, Publications de Mireille Bousquet-Mélou

M. Bousquet-Mélou, Sorted or sortable permutations, Discrete Math., 225 (2000), 25-50.

J. West, Sorting twice through a stack, Theoret. Comput. Sci. 117 (1993) 303-313.

Index entries for sequences related to sorting

Crossrefs

Cf. A027432.

Sequence in context: A051625 A056098 A239201 * A101971 A211387 A303952

Adjacent sequences: A027358 A027359 A027360 * A027362 A027363 A027364

Keyword

nonn,nice

Author

Mireille Bousquet-Mélou

Extensions

Prepended a(0)=1 to match offset, added more terms, Joerg Arndt, Jul 01 2014

Status

approved