5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Bob May 9 '15 at 16:15
  • $\begingroup$ Someone told me catalan number's is the answer. $\endgroup$ – Kishan Kumar May 9 '15 at 16:24
  • $\begingroup$ Is there a limit to the number of cars that can be on the spur track at once? $\endgroup$ – MisterEman22 May 9 '15 at 17:14
  • $\begingroup$ Nope. No limit is there $\endgroup$ – Kishan Kumar May 9 '15 at 17:18
6
$\begingroup$

I got my Answer

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

Plus you can see http://www.maths.usyd.edu.au/u/kooc/catalan/cat11rail.pdf and https://www.youtube.com/watch?v=m9Khxn2g-6w

The first link will explain that it is same as matching parentheses and the second link that how this leads to catalan's number

$\endgroup$
  • $\begingroup$ I got help from Math's SE site where someone answered my query. $\endgroup$ – Kishan Kumar May 9 '15 at 18:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.