Permutation At A Railway Track

Engines numbered 1, 2, ..., n are on the line at the left, and it is desired to rearrange(permute) the cars as they leave on the right-hand track. An engine that is on the spur track can be left there or sent on its way down the right track, but it can never be sent back to the incoming track. For example if n = 3, and we ha the engines numbered 1,2,3 on the left track, then 3 first goes to the spur track. We could then send 2 to the spur, then on the way to its right,then send 3 on the way, then 1, obtaining the new order 1,3,2. We have to find all the possible permutations for specific n.

Didn't find any generality.

• Do you have answers for other values of $n$? I'm sure someone here could spot a general formula in seconds if you posted a few more values.
– Bob
May 9 '15 at 16:15
• Someone told me catalan number's is the answer. May 9 '15 at 16:24
• Is there a limit to the number of cars that can be on the spur track at once? May 9 '15 at 17:14
• Nope. No limit is there May 9 '15 at 17:18

Thus, a plan for what you do will be some mixture of $n$ "put a car into the spur" operations and $n$ "take a car out from the spur" operations. Two different sequence of operations will always lead to different permutations (why?), and a sequence of operation is valid if no prefix of it has more "take out from spur" operations in it than it has "put into spur" operations.
This means that every valid operation sequence corresponds uniquely to a string of matching parentheses of length $2n$, and the number of such strings is the Catalan number $C_n=\frac1{n+1}\binom{2n}n$.