TITLE: matching problem
QUESTION [0 upvotes]: Suppose that there is an absented-minded secretary, there are $n$-letters and $n$-corresponding letter. The secretary puts the letters in any corresponding, and not necessary it's corresponding envelope. What is the probability that there is at least one match? Find the limit if this probability as $n$ approaches infinity. (You are not allowed to use dearrangements or conditional probabilities.)
What I have done is:
Let $A$ denote "there is at least one match," $A^-$ denote "there isn't any match," and $S$ denote the whole sample space.
$$P(S)=P(A)+P(A^-)$$
$$P(A)=P(S)−P(A^-)$$
$$P(A)=1−P(A^-)$$
The probability of $P(A^-)$ is $_{2n}C_{n}$, where $C$ denotes combination.
Am I correct so far or am I stuck?

REPLY [1 votes]: We consider "there isn't any match", let $ a_{n} $ represent the ways of all the $ n $ letters are not match. When we consider $ a_{m+1} $, there are two cases with the $ (m+1)_{th} $ letter:
case1: The $ (m+1)_{th} $ letter is in the $ k_{th} $  box, and the $ (k)_{th} $ letter is in the $ (m+1)_{th} $  box, where $ 1 \leq k \leq m $. There are $ m \cdot a_{m-1} $ ways in total;
case2: The $ (m+1)_{th} $ letter is in the $ k_{th} $  box, and the $ (k)_{th} $ letter isn't in the $ (m+1)_{th} $  box, where $ 1 \leq k \leq m $. There are $ m \cdot a_{m} $ ways in total.
So we get recurrence $ a_{m+1} = m \cdot (a_{m} + a_{m-1}) $, the problem is easy to solve.
{"set_name": "stack_exchange", "score": 0, "question_id": 490229}