Permutation At A Railway Track !Switching Network 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. For n=1, answer = 1; For n=2 answer = 2; For n=3 answer = 5; Didn't find any generality.

You can ignore the straight track; sending a car through it is equivalent to putting it onto the spur and taking it out immediately. (At least if you don't care about which orientation the cars end up in).

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$.