Combinatorics Matching Problem

Feb 2015
9
0
Dusseldorf
There are n different elements randomly assigned to n different spots. There is exactly one "correct" spot for each element. What is the probability that at least one element is assigned to its "correct" spot?

My idea was:
$1-P(\text{No element is assigned to its correct spot})=1-\frac{(n-1)!}{n!}=\frac{n-1}{n}$

Numerator: For the first Element there are n-1 incorrect spots, for the second there are n-2 incorrect spots, ... . So alltogether (n-1)! possible incorrect assignments

Denominator: I can assign the first element to n spots, the second to (n-1) spots, ... . So alltogether n! possible assignments

Apparently this solution is wrong. I understand correct solution ($1-\frac{1}{e}$ as n tends to infinity) and its derivation but I don't understand why my idea leads to an incorrect answer.

Thanks for your help!
 

Plato

MHF Helper
Aug 2006
22,492
8,653
There are n different elements randomly assigned to n different spots. There is exactly one "correct" spot for each element. What is the probability that at least one element is assigned to its "correct" spot?
My idea was:
$1-P(\text{No element is assigned to its correct spot})=1-\frac{(n-1)!}{n!}=\frac{n-1}{n}$
A well known and studied problem. Lookup derangements
\(\displaystyle \displaystyle{{D_n} = \frac{1}{{n!}}\sum\limits_{k = 0}^n {\frac{{{{\left( { - 1} \right)}^k}}}{{k!}}} \approx \frac{{n!}}{e}}\)

Given $J$ labeled objects and $J$ positions, $1-\dfrac{D_J}{J!}$ is the probability that at least one is correctly placed.
 
  • Like
Reactions: 1 person
Similar Math Discussions Math Forum Date
Discrete Math
Discrete Math
Discrete Math
Discrete Math