Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
This is equivalent to "probability that exactly k cards stay in the same place after shuffling" See here: johndcook.com/blog/2010/04/06/subfactorial –  leonbloy Sep 17 '12 at 14:01
    
Wow, you're right! This is basically the same problem with 52 cards numbered 1 through 52. The solution's so elegant... wow. Do you know of a proof/derivation for it? –  David Faux Sep 17 '12 at 14:06
    
This is sometio –  digital-Ink Sep 17 '12 at 14:41

3 Answers 3

up vote 4 down vote accepted

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

share|improve this answer
    
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. –  Michael Chernick Sep 17 '12 at 15:22

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

share|improve this answer

See Partial derangements or Rencontres numbers

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.