(b) Please evaluate the length of the shortest path. (5%)

5. The derangement problem can be described as the following story. Assume that there are five customers who hand over their hats to the waiter at the restaurant. After the dinner, the waiter gives them back the hats at random. If the return order is , it is not a derangement because this order leaves fixed. However, if the return order is , we say that it is a derangement because no element is left in its original position. That means no customer can receive the correct hat. Please prove that the probability of derangement of a set with n elements converges to as n grows without bound. (Hint: Applying the inclusion-exclusion principle) (15%)

題組內容

(b) Please evaluate the length of the shortest path. (5%)

相關申論題

相關試卷