Inclusion–exclusion principle
Counting derangements

A more complex example is the following.

Suppose there is a deck of n cards numbered from 1 to n. Suppose a card numbered m is in the correct position if it is the m card in the deck. How many ways, W, can the cards be shuffled with at least 1 card being in the correct position?

Begin by defining set A, which is all of the orderings of cards with the m card correct. Then the number of orders, W, with at least one card being in the correct position, m, is

Apply the principle of inclusion–exclusion,

Each value A m 1 ∩ ⋯ ∩ A m p {\displaystyle A_{m_{1}}\cap \cdots \cap A_{m_{p}}} represents the set of shuffles having at least p values m,..., m in the correct position. Note that the number of shuffles with at least p values correct only depends on p, not on the particular values of m {\displaystyle m}. For example, the number of shuffles having the 1, 3, and 17 cards in the correct position is the same as the number of shuffles having the 2, 5, and 13 cards in the correct positions. It only matters that of the n cards, 3 were chosen to be in the correct position. Thus there are (n p) {\textstyle {n \choose p}} equal terms in the p summation (see combination).

| A 1 ∩ ⋯ ∩ A p | {\displaystyle |A_{1}\cap \cdots \cap A_{p}|} is the number of orderings having p elements in the correct position, which is equal to the number of ways of ordering the remaining n − p elements, or (n − p)!. Thus we finally get:

A permutation where no card is in the correct position is called a derangement. Taking n ! to be the total number of permutations, the probability Q that a random shuffle produces a derangement is given by

a truncation to n + 1 terms of the Taylor expansion of e. Thus the probability of guessing an order for a shuffled deck of cards and being incorrect about every card is approximately e or 37%.
keywords:frequency, detectable_format:number_highlighted_sections[3]