Problem:
Suppose that cards numbered 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 are picked up on the first pass, and on the second pass, on the third pass, on the fourth pass, and on the fifth pass. For how many of the possible orderings of the cards will the cards be picked up in exactly two passes?
Answer Choices:
A.
B.
C.
D.
E.
Solution:
Choose a subset of , and place the cards numbered in increasing order in the spots determined by . Then place the remaining cards in increasing order in the remaining (complementary) spots. The resulting arrangement of cards will be picked up in at most two passes, and any other arrangement will require more than two passes. There are choices for the subset , but any subset of the form will result in the cards being picked up in one pass. There are 14 such "initial block" subsets ( that result in picking up the cards in one pass. This gives possible orderings requiring exactly two passes.
For each integer , let be the number of ways to arrange the 13 cards so that cards 1 through are selected in the first pass with 1 or more cards left for a second pass. Observe that there are locations at which these cards can appear in the sequence, and within these locations the cards must appear in increasing order. The remaining cards will occupy the remaining slots; because these cards will be selected in the second pass, they must appear in increasing order. As long as the first cards do not occupy the first spots in the sequence, two passes will be required to pick up all the cards. Thus . The total number of ways over all values of is
For let denote the position of the number in the list. Thus in the provided example, , and so on. If , then the cards numbered are picked up on the same pass. However, if , then that pass is complete, and a new pass is required to pick up the card numbered . The sequence of numbers is said to have a drop at when . The total number of passes required to pick up all 13 cards is one more than the number of drops in the sequence of numbers .\
Let denote the number of permutations of the numbers that have exactly one drop. If is a permutation of the numbers with exactly one drop, then a permutation of the numbers with exactly one drop can be created either by inserting at the\
position of the drop, or by placing at the righthand end of the sequence that defines . Thus a permutation of the type generates two permutations of the type . Now let be the permutation with no drop. A permutation on with exactly one drop can be created by inserting either before 1 , or between 1 and 2 , or , or between and , which is a total of places. Thus
Because and , it follows by induction that , and hence the answer is .
Note: Let
denote the number of permutations of that can be picked up in exactly passes. By generalizing the reasoning found above, it can be shown that these numbers are generated by the Pascal-like recurrence
These are the Eulerian numbers. Like the binomial coefficients, they have a symmetry:
Because these numbers count permutations in various classes,
However, unlike binomial coefficients, for which there exists a closed-form formula in terms of factorials, there seems to be no simple closed-form formula for the Eulerian numbers, although
The special case is what was derived.
The problems on this page are the property of the MAA's American Mathematics Competitions