How to use the derangement probability calculator
- Enter the number of items that are shuffled, up to 1,000. These might be people in a gift exchange, letters and envelopes, or cards.
- Leave items left in place at 0 to count shuffles where nothing stays put, or enter a number to count shuffles with exactly that many matches.
- Read the count, the chance among all shuffles, the chance of at least one match and the table for 0 to 6 matches.
- Large counts are shown as digits times a power of ten. The CSV download holds every digit.
Formula
D(n) = (n - 1) x (D(n - 1) + D(n - 2)), with D(0) = 1 and D(1) = 0
chance of no match = D(n) / n!
exactly k in place: C(n, k) x D(n - k) shuffles
for n at least 1, D(n) is the nearest whole number to n! / e
A shuffle with no item in its own place is called a derangement. The counts are exact whole numbers computed with big-number arithmetic.
Eight names in a hat
With 8 items there are 8! = 40,320 shuffles, and D(8) = 14,833 of them leave nothing in place. The chance is 14,833 / 40,320 = 0.3678819444, so the chance that at least one item lands in its own place is 0.6321180556. With 6 items, the numbers of shuffles with exactly 0, 1, 2, 3, 4, 5 and 6 fixed items are 265, 264, 135, 40, 15, 0 and 1, which add up to 720.
The chance does not keep falling as the group grows. It settles near 1 / e = 0.3679. For 1,000 items D(1000) has 2,568 digits and begins 1.48030 x 10^2567.
Why the answer settles
Each item has a 1 in n chance of landing in its own place, and there are n items, so you might expect the chance of at least one match to grow with n. The two effects cancel: the expected number of matches is exactly 1 for every n, and the chance of none approaches 0.3679 very quickly. For 5 items it is already 0.3667.
A one-item shuffle has D(1) = 0, because the only arrangement leaves the item in place. That is why gift exchanges with a single pair cannot avoid a match.
Using it for gift exchanges
In a gift exchange where each person draws one name, the draws that leave nobody with their own name are exactly the derangements, so the chance that a simple reshuffle-until-valid method is needed is 1 minus D(n) / n!. The Secret Santa generator makes a valid draw for you. For counting arrangements in general, see the combinations and permutations calculator and the probability calculator.
Assumptions and limits
- The items are all different and every shuffle is equally likely.
- The number of items is a whole number from 1 to 1,000, and the number left in place is a whole number from 0 to n.
- Counts are exact. Probabilities are shown to ten decimal places, rounded half up.
- The page counts arrangements. It does not model any game, bet or draw rules beyond the plain shuffle.
Frequently asked questions
What is a subfactorial?
It is another name for the number of derangements, written !n. The recurrence on this page is the usual way to compute it, and !n is the nearest whole number to n! divided by e.
Why is the chance of exactly n - 1 matches always zero?
If n - 1 items are in their own places, the last item has only one place left, which is its own. So it cannot be the only one out of place. The table shows that zero for 5 matches in a shuffle of 6.
How can the count have thousands of digits?
The page uses exact big-number arithmetic, so no digits are lost. A shuffle of 1,000 items has more than 2,500 digits in its count.
Does this apply to cards?
Yes, if you ask for the chance that a shuffled deck puts no card in the position where it started. For a 52-card deck that is about 0.3679, the same as for any large group.