Guoce Xin
Knuth's stack sorting operation for permutations is naturally extended for sequences of integers. A partition or a matching is said to be k-stack sortable if its canonical sequence is. We find that a partition is k-stack sortable if and only if it is 23...(k+2)1-avoiding. Then k-stack sortable matchings and partitions are enumerated. We show that their generating functions are rational. Matchings and partitions classified by noncrossing and nonnesting are also considered.