Consider the following railroad switching network:
Railroad cars numbered 1,2, ..., n on the right track are to be permuted and moved along on the left track. As described in Problem 2 of Section 7.1, a car may be moved directly onto the left track, or it may be shunted onto the siding to be removed at a later time and placed on the left track. The siding thus operates like a stack, a push operation moving a car from the right track onto the siding and a pop operation moving the "top" car from the siding onto the left track.
a. For n = 3, find all possible permutations of cars that can be obtained (on the left track) by a sequence of these operations. For example, push 1, push 2, move 3, pop 2, pop 1 arranges them in the order 3, 2,1. Are any permutations not possible?
b. Find all possible permutations for n = 4. What permutations (if any) are not possible?
c. Repeat (b) for n = 5.
d. Challenge: In general, what permutations of the sequence 1,2, ..., n can be obtained when a stack is used in this manner?