Originally Posted by

**hockey777** I need to list all the Stack-Sortable Permutations for n=4. I know it will be 14 as it moves with the Catalan numbers, but I really don't understand the definition.

Cn is the number of stack-sortable permutations of {1, ..., n}. A permutation w is called stack-sortable if S(w) = (1, ..., n), where S(w) is defined recursively as follows: write w = unv where n is the largest element in w and u and v are shorter sequences, and set S(w) = S(u)S(v)n, with S being the identity for one-element sequences.

If anyone can help me out, that would be great.

Thanks!