Question:
Suppose that 13 cards numbered 1, 2, 3, … 13 are arranged in a row. The task is to pick them up in numerically increasing order, working repeatedly from left to right. In the example below, cards 1, 2, 3 are picked up on the first pass, 4 and 5 on the second pass, 6 on the third pass, 7, 8, 9, 10 on the fourth pass, and 11, 12, 13 on the fifth pass. For how many of the 13! possible orderings of the cards will the 13 cards be picked up in exactly two passes?
7, 11, 8, 6, 4, 5, 9, 12, 1, 13, 10, 2, 3
Solution:
For each position we can put the cards in, we can choose for it to be picked up in the first or second pass. With a given order of first/second pass, there is only one possible solution.
For example.
1st/2nd pass: 2, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 2, 1
Number: 10, 1, 2, 3, 11, 4, 12, 5, 6, 7, 8, 13, 9
This gives 213 solutions. However, when all of the cards in the 1st pass are before all of the cards in the 2nd pass, the list is in a strictly increasing consecutive order, meaning the cards can be picked up in one pass. There are 14 ways this can happen so the answer is:
213 – 14 = 8178