Stacked Carts

Let us try a recursive solution first:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

n = 16
result = 0

def count(spur, right):
  if right == n:  #all trains are on the right track
    result++
  elif right + spur < n: #there is at least one train available on the left track
    count(spur+1, right) #push a cart
  if spur > 0: #if the spur is non-empty
    count(spur-1, right+1) #pop a cart

count(0,0)
print result

But that is probably an inefficient solution. Let's try something else.

Consider any valid sequence of push and pop . The following must be true:

• There are as many push es as pop s. Otherwise, we'd get a stackoverflow or keep a cart in the spur forever.
• No cart can be pop ed before it was push ed.

And now consider the well known properties of bracketed sequences like (())()() . They have the same rules:

• There are as many ( as ) .
• There is no ) that precedes its corresponding ( .

So, if we replaced pop s and push es with ( and ) , we'd get a bracketed sequence.

As we are aware of, the number of such sequences are the Catalan Numbers

As a Dynamic Programming lover, my solution is a little different from Agnishom's.

Let $dp(i)$ be the number of permutations we can have for $i$ carts. Clearly, $dp(0) = dp(1) = 1$ . For $i>1$ , we have the following recurrence relation,

$dp(i)=\sum_{j=0}^{i-1} dp(j) * dp(i-j-1)$

Why does this work? When we added another element, consider the moment it goes to the right track. if it is on the $j^{\text{th}}$ position (0-indexed) that means there are $j$ elements infront of it and they have $dp(j)$ number of permutations which we have already compute. Similarly, behind it will have $i-j-1$ elements with $dp(i-j-1)$ number of permutations.