2
$\begingroup$

There are 5 balls numbered 1 to 5 and 5 boxes numbered 1 to 5. The balls are kept in the boxes one in each box. What is the probability that exactly 2 balls are kept in the corresponding numbered boxes and the remaining 3 balls in the wrong boxes?

I have figured out that the number of ways for putting 2 balls in correct numbered box is 5C2 but I cant figure out how to calculate for remaining 3 balls? Thanks in advance!

$\endgroup$
0
$\begingroup$

There are $5!$ ways to arrange the five balls into the five boxes, in total.

I have figured out that the number of ways for putting 2 balls in correct numbered box is $^5C_2$ but I cant figure out how to calculate for remaining 3 balls? Thanks in advance.

To arrange for 2 balls to be "good" and 3 balls "bad", we need to select which two from the five balls as good, put each in their own box, the make sure the three remaining balls are bad we take any one of them and select one from the two other balls' box to put it in, then just take the ball for that box and put it in the last ball's box so that the last ball will also go into the wrong box.

Basically you want to calculate how many ways to rearrange $ABC$ so they are all in the wrong position, such as $BCA$ , $CAB$, or... wait that's it.

$\endgroup$
  • $\begingroup$ So what is the mathematical approach to this question? $\endgroup$ – Priyank Feb 10 '17 at 12:20
  • $\begingroup$ That is the mathematical approach, @Priyank . Though for a more general solution you can research the topic of "derangement". $\endgroup$ – Graham Kemp Feb 10 '17 at 14:18
  • $\begingroup$ Ok thanks for the help. I understood your explanation but can you tell me exactly how to implement the theory in question? $\endgroup$ – Priyank Feb 10 '17 at 18:35
  • $\begingroup$ It is ${^5\mathrm C_2} \cdot !3$ $\endgroup$ – Graham Kemp Feb 11 '17 at 0:56
0
$\begingroup$

I would like to demonstrate the solution of this problem with generating functions, in order to illustrate how to combine generating functions with the inclusion/exclusion principle. This is rather like smashing a small nut with heavy machinery, but sometimes it is convenient to have a small example for the purpose of illustration; so I hope I may be forgiven for what is surely overkill.

There are 5! possible arrangements of the balls in the boxes, all of which we assume are equally likely. In order to solve the OP, we need to count the number of arrangements in which exactly 2 balls are in their proper boxes, i.e. the boxes with the same numbers as the balls.

Let's say an arrangement of the balls in the boxes has "Property $i$" if ball $i$ is in box $i$. Let $N_r$ be the number of arrangements which have $r$ of the properties, with over-counting. (Here we diverge from the usual notation in inclusion/exclusion problems: usually the symbol used is $S_r$, but in this case I am going with the notation used in Wilf's generatingfunctionology in its discussion of inclusion/exclusion; see the reference below.) Then it's easy to see that $$N_r = \binom{5}{r} (5-r)!$$ for $r=0,1,2,3,4,5$. We define $f(x)$, the generating function of $N_r$, by $$f(x) = \sum_r N_r x^r$$ Computing the values of the $N_r$'s, we have $$f(x) = 120 + 120 x + 60 x^2 + 20 x^3 + 5 x^4 + x^5$$ Now comes the trick! $f(x-1)$ is the generating function of $e_r$, where $e_r$ is the number of arrangements with exactly $r$ of the properties. So we compute $$f(x-1) = 44 + 45x + 20 x^2 + 10 x^3 + x^5$$ This shows there are 44 arrangements with no balls in their proper boxes, 45 arrangements with 1 ball in its proper box, 20 arrangements with 2 balls in their proper box, 10 arrangements with 3 balls in their proper boxes, and 1 arrangement with all 5 balls in their proper boxes. Notice that the coefficient of $x^4$ is zero, i.e. there are no arrangements with exactly 4 balls in their proper boxes. This is obvious when we think about it, but the generating function gave us this result automatically--no thought required.

With all this behind us, the solution to the original problem--the probability that exactly 2 balls are in their proper boxes-- is $20 / 5!$.

Reference: generatingfunctionology by Herbert S. Wilf, section 4.2, "A generatingfunctionological view of the sieve method"

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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