What's the probability that 7 balls are in their proper positions? I have 12 balls labeled from 1 to 12 in a bag. I randomly draw 12 times from this bag. Every time I draw a ball, I append it to the right of a line. The balls in the line are ordered from the left, so the leftmost ball is first in line. At the end of this, a ball is in its proper position if its order matches its label. For instance, ball 5 is in its proper position if it's 5th in line.
What's the probability that 7 balls are in their proper positions?
I tried just taking ${12}\choose{7}$ since it does matter which specific orders have balls matched. However, I just realized that the draws depend on each other. For instance, if 11 balls are in proper positions, the last one must be in proper positions. What in probability can I latch onto to solve this problem? 
 A: As others have remarked it is explained in every book on combinatorics that the number $D_n$ of permutations in $S_n$ having no fixed point is given by
$$D_n=n! \sum_{k=0}^n (-1)^n/n!\ \doteq n!{1\over e}\ .\qquad(*)$$
In our case there are five cards that have to be misplaced, and the other seven cards should stay in place. There are ${12\choose5}$ ways to select the five cards, and for each selection there are approximatively $5!{1\over e}$ admissible permutations. Since the total number of permutations is $12!$, the probability $P$ that a random permutation keeps exactly $7$ cards in place is approximatively given by
$$P\ \doteq\ {{12\choose 5}\cdot 5!{1\over e}\over 12!}={1\over 7!\ e}\doteq 0.000073\ .$$
Here is a sketch of proof of the formula $(*)$:
A permutation $\pi\in S_n$ has no fixed points iff all its cycles have length $\geq2$. Consider such a $\pi$. When the number $n$ appears in a cycle of length $\geq3$ immediately after some number $k\in[n-1]$ we can omit it there and obtain the cycle representation of a fixed-point free $\pi'\in S_{n-1}$. If the number $n$ appears in a $2$-cycle together with some $k\in[n-1]$ we can omit the cycle $(k,n)$ from the representation of $\pi$ and obtain the cycle representation of a $\pi''\in S_{n-2}$. All in all one can convince oneself that the $D_n$ satisfy the recursion
$$D_n= (n-1)(D_{n-1}+D_{n-2})\ .$$
This implies
$$D_n-n D_{n-1}=-\bigl(D_{n-1}-(n-1)D_{n-2}\bigr)\ ,$$
or
$$D_n-nD_{n-1}=(-1)^{n-1}\bigl(D_1-D_0\bigr)=(-1)^n\ ,$$
as $D_0=1$, $D_1=0$. The last recursion easily implies $(*)$.
A: See Partial derangements or Rencontres numbers 
A: The number of ways you can arrange (permute) $n$ objects, labeled from $1$ to
$n$, in a sequence such that no object is on the exact position as its label
is
$$
D_{n}=n!\sum_{k=0}^{n}\frac{(-1)^{k}}{k!}
$$
and can be proven in several ways (this is sometimes referred to as the
derangement problem). In your case you need to compute the number of
permutations of $12$ objects (labeled from $1$ to $12$) such that $7$ objects
are in place and the rest ($5$) are misplaced (the label and the position in
the sequence are different for each of the $5$ objects). So in your case,
first you need to choose $7$ objects to put in their exact position (this is
done in $\dbinom{12}{7}=\dfrac{12!}{5!7!}$ ways), then the remaining $5$ must
be put in a "derangement" (and this is done in $D_{5}$ ways). So the answer
is
$$
\dbinom{12}{7}D_{5}=\dfrac{12!}{5!7!}\cdot5!\sum_{k=0}^{5}\frac{(-1)^{k}}
{k!}=\frac{12!\sum_{k=0}^{5}\frac{(-1)^{k}}{k!}}{7!}=34\,848
\text{,}
$$
while the associated probability is
$$
\frac{\dbinom{12}{7}D_{5}}{12!}=\frac{\sum_{k=0}^{5}\frac{(-1)^{k}}{k!}}
{7!}=7.\,2751\times10^{-5}
$$
