1. ## Stack-Sortable Permutations

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!

2. This seems to be an interesting problem.
But I have no idea from you description what a stack-sortable permutation would be.
Can you expand on the definition?

3. 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!
I'm not sure I understand the problem, but here is my take on it, on the theory that some help is better than no help at all (however ill-informed)--

Let e = the empty string. The problem statement from the MIT site says S(e) = e.

S(1) = S(e1e) = S(e)S(e)1 = ee1 = 1
(one SSP)

S(12) = S(12e) = S(1)S(e)2= 1e2 = 12
S(21) = S(e21) = S(e)S(1)2 = e12 = 12
(one SSP)

S(123) = S(123e) = S(12)S(e)3 = 123
S(231) = S(2)S(1)3 = 213
S(312) = S(e312) = S(e)S(12)3 = 123
S(321) = S(e321) = S(e)S(21)S(3) = 123
S(213) = S(213e) = S(21)S(e)3 = 123
S(132) = S(1)S(2)3 = 123
(two SSPs)

If you follow this pattern and work out the possibilities for all 24 permutations of 1234, I think you will find 5 SSPs: 1234, 1324, 2134, 2314, and 3124.

(What this has to do with stacks or sorting is still a mystery to me, though.)

jw