Stacked CartsComputer 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
pushpushes cart 3 to the spur track.
poppops cart 3 to the right track.
pushpushes cart 2 and cart 1 to the spur track.
poppops 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\)