Permutation At A Railway Track(Stack Implementation)

Question

Engines numbered 1, 2, ..., n are on the line at the left, and it is desired to rearrange(permute) the engines 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. Using Stack Implementation would be very helpful.

But any solution is welcomed.

p.s. This is not a homework question, as I am a self taught person.

Answer 1

Here's my attempt at a recursive solution (see comments in Java code):

private static int result = 0;
private static int n = 3;

public static void g(int right,int spur){
  if (right == n) // all trains are on the right track
    result++;
  else if (right + spur < n) // some trains are still on the left track
    g(right,spur + 1); // a train moved from the left track to the spur
  if (spur > 0) // at least one train is on the spur
    g(right + 1,spur - 1); // a train moved from the spur to the right track 
               // (also counts trains moving directly from the left to right track)
}

public static void main (String[] args){ 
  g(0,0);
  System.out.println(result); // 5
}

The recursive solution above actually counts each possibility. For a combinatorial solution we consider all combinations of n movements on and out of the spur, where adjacent such movements are equivalent to movements directly from the left to right track. There are 2n choose n such combinations. Now let's count the invalid ones:

Consider all combinations of (n - 1) ins and (n + 1) outs of the spur. All these include a point, p, where a train is counted as leaving the spur when no trains are on it. Let's say that p has k ins and (k + 1) outs preceding it - then the number of remaining ins is (n - 1 - k); and remaining outs, (n + 1) - (k + 1) = (n - k).

Now reverse the ins and outs for each one of these combinations starting after p so that in becomes out and out in. Each one of the reversed sections has necessarily (n - k) ins and (n - 1 - k) outs. But now if we total the number of ins and outs before and after p we get k + (n - k) = n ins, and (k + 1) + (n - 1 - k) = n outs. We have just counted the number of combinations of n ins and n outs that are invalid. If we assume that one such combination may not have been counted, theoretically reverse that combination after its p and you will find a combination of (n - 1) ins and (n + 1) outs that was not counted. But by definition we counted them all already so our assumed extra combination could not exist.

Total valid combinations then are 2n choose n - 2n choose (n + 1), the Catalan numbers.

(Adapted from an explanation by Tom Davis here: http://mathcircle.berkeley.edu/BMC6/pdf0607/catalan.pdf)