A deck of N cards is numbered 1 to N and shuffled. If dealt from top to bottom, what is the probability of dealing at least one pair of successive cards in their proper order (i.e a 4 followed by a 5, at any position in the deck.) For N=2, 3, 4, the probabilities are 1/2, 1/2, 13/24. Solve for N up to 10 (or higher). Does the probability ever decrease or is there a limit as N increases?
Extension: What is the expected number of such successive pairs in an N card deck? (Pairs may overlap: 52341 has two successive pairs - 23 and 34.)
Source: Mark Moyer from UVM, citing practical experience with the random order of submitted homework assignments.First, it was quickly pointed out to me that the number of ways to arrange the deck so that no successive pairs occur is 1, 1, 3, 11, 53, 309, 2119, ... is sequence A000255 in the On-Line Encyclopedia of Integer Sequences. The probability of finding at least one pair is just (N-x)/N! (where x is the entry from the sequence), giving:
1/2, 1/2, 13/24, 67/120, 411/720, 2921/5040, 23633/40320, 214551/362880, 2160343/3628800, ...
The probability is always increasing and approaches 1 - 1/e.
Joseph DeVincentis described the expected number in this way: There are N-1 possible pairs in an N card deck. For any given pair, the probability of it occurring is [(N-1)/N] *[1/(N-1)] = 1/N. (The first term is the chance that the first card of the pair is not on the bottom, since we do not count pairs that wrap around from the bottom of the deck to the top. The second term is the chance, given that there is a card below the first card, that it is the correct one of the N-1 other cards.) So the expected number of pairs is (N-1)/N = 1 - 1/N.