Stacked Carts

Computer Science Level 4

There are carts arranged from 1 to \(N\) on the left track. There are two commands available to the operator:

  • push: move the rightmost cart from the left track to the top of the spur track
  • pop: move the topmost cart from the spur track to the right track.

Using these commands, in how many ways can we permute the carts as they are being queued up in the right track? Assume there are 16 carts.

For example, let us say there are 3 carts. Consider the sequence of commands push, pop, push, push, pop, pop

  • push pushes cart 3 to the spur track.
  • pop pops cart 3 to the right track.
  • push pushes cart 2 and cart 1 to the spur track.
  • pop pops cart 1 and cart 2 to the right track.

The new sequence of carts on the right track is [2, 1, 3].

It turns out, that there are 5 ways the new sequence of carts can be in, when \(N = 3\)


Problem Loading...

Note Loading...

Set Loading...