Ken's Puzzle of the Week

Cards in Order

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.
Mail to Ken