Please forgive my if someone has already asked this.
Imagine there are $n$ cards each with their backs facing up. Each time we randomly pick a card and turn it over, but once we pick a card that has already been turned over, all the cards revert back to face-up. What is the expected value of times needed to turn over all the $n$ cards?
My thought is that, if there are already $k<n$ cards turned over, then after the next step we will have $k+1$ cards turned over with probability $\dfrac{n-k}{n}$, and all cards reverting with probability $\dfrac{k}{n}$. As a result, the transition matrix between the states that indicate the number of cards turned over is $$ \begin{pmatrix} 0 & \dfrac{1}{n} & \cdots & \dfrac{n-1}{n} & 0 \\ 1 & 0 & \cdots & 0 & 0 \\ 0 & \dfrac{n-1}{n} & \cdots & 0 & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & \cdots & \dfrac{1}{n} & 1 \end{pmatrix} $$ But I don't know if this helps to find the expected value of times to reach the state with all cards turned over. Also, I wrote a program to check with $n=2,3,4,5$ and I guess that the answer is $\displaystyle\sum^{n}_{k=1}\dfrac{n^k}{k!}$ (that is, $4$ for $n=2$, $12$ for $n=3$, $\dfrac{100}{3}$ for $n=4$ and $\dfrac{1085}{12}$ for $n=5$), so I would like to have a combinatorial explanation. Thanks for any help.
Edit: Well the original question can be easily solved using the total expectation. But still, I'm interested in an explanation for the form $\displaystyle\sum^{n}_{k=1}\dfrac{n^k}{k!}$. Where does each term $\dfrac{n^k}{k!}$ come from, for example?
Well, it occurs to me that the answer is so easy: just consider the case where the first failure occurs at the $k$-th place, which has probability $\dfrac{n}{n}\dfrac{n-1}{n}\cdots\dfrac{n-(k-2)}{n}\dfrac{k-1}{n}=\dfrac{n!(k-1)}{(n-(k-1))!n^k}$, so the expected value $E$ satisfies: $$ E = \dfrac{n!}{n^n}\times n+\sum^{n}_{k=1}\dfrac{n!(k-1)}{(n-(k-1))!n^k}(E+k), $$ (the first term is the case where we succeed immediately) or $$ \left(1-\sum^{n}_{k=1}\dfrac{n!(k-1)}{(n-(k-1))!n^k}\right)E=\dfrac{n!}{n^n}\times n+\sum^{n}_{k=1}\dfrac{n!(k-1)k}{(n-(k-1))!n^k}. $$ The LHS is $$ 1-\sum^{n}_{k=1}\dfrac{n!(n-(n-(k-1)))}{(n-(k-1))!n^k}=1-\left(\sum^{n}_{k=1}\dfrac{n!}{(n-(k-1))!n^{k-1}}-\sum^{n}_{k=1}\dfrac{n!}{(n-k)!n^k}\right)=\dfrac{n!}{n^n}, $$ hence $$ E=n+\sum^{n}_{k=1}\dfrac{n^{n-k}(k-1)k}{(n-(k-1))!}\overset{n-(k-1)=j}{=}n+\sum^{n}_{j=1}\dfrac{n^{j-1}(n-j)(n-j+1)}{j!}, $$ and \begin{align*} E-\sum^{n}_{k=1}\dfrac{n^k}{k!}&=n+\sum^{n}_{k=1}\dfrac{n^{k-1}(n^2-2kn+k(k-1))}{k!}=n+\sum^{n}_{k=1}\dfrac{n^{k+1}}{k!}-2\sum^{n}_{k=1}\dfrac{n^k}{(k-1)!}+\sum^{n}_{k=2}\dfrac{n^{k-1}}{(k-2)!}\\ &=\sum^{n}_{k=0}\dfrac{n^{k+1}}{k!}-2\sum^{n-1}_{k=0}\dfrac{n^{k+1}}{k!}+\sum^{n-2}_{k=0}\dfrac{n^{k+1}}{k!}=\dfrac{n^{n+1}}{n!}+\dfrac{n^n}{(n-1)!}-2\dfrac{n^n}{(n-1)!}=0. \end{align*}