Results 1 to 4 of 4

Math Help - Stack-Sortable Permutations

  1. #1
    Junior Member
    Joined
    Feb 2008
    Posts
    48

    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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,962
    Thanks
    1784
    Awards
    1
    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?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2008
    Posts
    48
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Mar 2008
    Posts
    934
    Thanks
    33
    Awards
    1
    Quote Originally Posted by hockey777 View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Height of chimney stack using Angles of Elevation
    Posted in the Trigonometry Forum
    Replies: 2
    Last Post: April 30th 2011, 01:10 AM
  2. Stack automata
    Posted in the Discrete Math Forum
    Replies: 16
    Last Post: August 27th 2010, 05:28 AM
  3. Stack Variables & Simplex Tableau
    Posted in the Advanced Applied Math Forum
    Replies: 3
    Last Post: November 4th 2008, 07:19 AM
  4. Stack Variables & Simplex Tableau
    Posted in the Pre-Calculus Forum
    Replies: 0
    Last Post: November 3rd 2008, 03:44 PM
  5. Permutations help me please
    Posted in the Statistics Forum
    Replies: 6
    Last Post: July 12th 2008, 09:11 PM

Search Tags


/mathhelpforum @mathhelpforum