2
$\begingroup$

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?

  • 0
    This is sometio2012-09-17

3 Answers 3

4

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 $(*)$.

  • 0
    The draw is a permutation of the numbers 1 to 12. The answer is the exact number of permutations with 7 in the cirrect position and 5 not divided by the total number of permutations. Since there are 12! permutations enumeration of them does not appear to be feasible. So you resort to the theory of permutations and combinations (combinatorics). It looks like Christian has given you a good approximate answer based on theory.2012-09-17
2

See Partial derangements or Rencontres numbers

2

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} $