Canada Math Contest #2 - Problem 11

In Wordland, every library has 10 shelves. Each shelf has some number of books, all with different names, in random order. Two libraries are considered different if there is some shelf with a different number of books. A shelf is called “near-sorted” if one of the following conditions is satisfied:

1. The shelf is empty.
2. All the books on the shelf are sorted in alphabetical order except for the book that comes first in alphabetical order, which must not come first in the arrangement.

For example, in a shelf with books A, B, C and D, the arrangements BACD and BCDA would be near-sorted, but the arrangements ABCD and ABDC would not. A library is called “near-perfect” if all of its shelves are near-sorted. Find the sum of the probabilities over all possible libraries that the library is near-perfect.