Dividing balls into boxes

Assume you have 6 workers (balls) and 5 working days (boxes).

What's the probability that two will take their vacation day on the same day if you know that they all have to take one vacation day per week?

I thought of thinking of the problem as dividing balls to boxes but what I came up to didn't seem to work:

Choose two as a block and sort the rest in a row: $${{6}\choose{2}} \times 2! \times 5!$$

-
–  usul Aug 12 '13 at 18:47
PHP means that at least two will be on the same day, I need exactly two –  Georgey Aug 12 '13 at 18:51
Do you mean it wil be a $2$-$1$-$1$-$1$-$1$ distribution? Or is $2$-$0$-$0$-$3$-$1$ allowed? Or a $2$, a $4$, the rest $0$? Also, even if that's OK, is $2$-$2$-$1$-$1$-$0$ allowed? Counting is no issue, even for general numbers, if it is clear what is being counted. –  André Nicolas Aug 12 '13 at 20:01

You could perhaps use the multinomial distribution http://en.wikipedia.org/wiki/Multinomial_distribution

It's a generalized version of the binomial theorem, where each trial (each worker's choice of vacation day) can fall into one of several categories (the day chosen). The probability mass function is

$f(x_1,...,x_5) = \frac{6!}{x_1! \cdots x_5!}p_1^{x_1}\cdots p_5^{x_5}$, where $x_1 + ... + x_5 = 6$ (otherwise, the probability is zero).

This would give, for example, $P(x_1$ days taken Monday, $x_2$ days taken Tuesday, ..., $x_5$ days taken Friday). So if we want the probability that exactly two workers take their vacation day on the same day, we need to sum this up over all nonnegative integer vectors $(x_1, ..., x_5)$ containing a 2 and summing to 6.

Now without these $p_k$'s, the problem isn't really solvable, but assuming each day is equally likely, we can call them (1/5), and reduce the formula to

$f(x_1,...,x_5) = \frac{6!}{x_1! \cdots x_5!} \left(\frac{1}{5}\right)^6$

Since our problem is small, it's feasible to just generate all nonnegative integer solutions to $x_1 + ... + x_5 = 6$ and toss out the orderings not containing a 2.

In Mathematica, we could do:

A = Select[FrobeniusSolve[{1,1,1,1,1},6],MemberQ[#,2]]

This generates all solutions to $x_1 + ... + x_5 = 6$ and selects those containing 2, and puts them in a table A.

Now for each entry in A, we can calculate $\frac{6!}{x_1! \cdots x_5!}$ with this function:

No[x_]:=Factorial[6]/Product[Factorial[Part[x,s]],{s,1,5}]

This divides 6! by $x_1! \cdots x_5!$ for an input $x = (x_1, ..., x_5)$. Now to add them up over each acceptable $x$ vector and multiply the result by (1/5)^6:

Sum[No[Part[A,j]],{j,1,Length[A]}]*(1/5)^6 = 96/125

-
Note that this does not require it to be (2,1,1,1,1), it could be any 5-valued set of nonnegative integers summing to 6 containing a 2. Note that counting arguments will probably work as well, and would be preferable in order to be realistically extensible to larger problems, but I'm not sure at the moment what the appropriate counting argument is. –  mach Aug 12 '13 at 23:01

We consider 3 possible interpretations of this question:

$\bf{A)}\;\;\textbf{Find the probability that at least two workers choose the same vacation day.}$

[This is the most immediate interpretation, and is related to the first comment made above.]

In this case, of course, we can apply the Pigeonhole Principle to conclude that the probability is 1.

$\bf{B)}\;\;\textbf{Find the probability that exactly two workers choose the same vacation day.}$

[Based on the OP's solution and comment above, this appears to be his intended interpretation.]

In this case, there is a 2-1-1-1-1 distribution; and there would be

5 ways to choose the shared vacation day, $\binom{6}{2}$ ways to choose the two workers who share that day, and $4!$ ways to choose the vacation days for the other workers, so

the probability would be $\frac{5\binom{6}{2}4!}{5^6}=\frac{72}{625}.$

$\bf{C)}\;\;\textbf{Find the probability that there is at least one day that is chosen by exactly two workers.}$

In this instance, we can consider 3 possible cases:

1) There is only one day chosen by exactly 2 workers.

$\;\;\;$ In this case, there are $\binom{6}{2}$ ways to choose the two workers who share that day, 5 ways to choose the $\;\;\;$day, and then

$\;\;\;$a) $4!$ ways to choose the days for the other workers if they all choose different days;

$\;\;\;$b) $\binom{4}{3}\cdot4\cdot3$ ways to choose the days for the other workers if 3 of them choose the same day and the $\;\;\;\;\;\;$last chooses another; and

$\;\;\;$c) 4 ways to choose the days for the others if they all choose the same day.

2) There are exactly two days that are chosen by exactly two workers.

$\;\;\;$In this case, there are $\binom{6}{4}\binom{3}{1}$ ways to select the two pairs of workers, and then $5\cdot4\cdot3\cdot2$ ways to $\;\;\;$assign the days for these two pairs and the other two workers.

3) There are 3 days that are chosen by exactly two workers.

$\;\;\;$Here there are $5\cdot3\cdot1$ ways to choose the 3 pairs, and then $5\cdot4\cdot3$ ways to assign days to these $\;\;\;$three pairs.

Therefore the probability that at least one day is chosen by exactly two workers is given by$$\frac{\binom{6}{2}\binom{5}{1}\big[4!+4\cdot4\cdot3+4\big]+\binom{6}{4}\binom{3}{1}\cdot5!+5\cdot3\cdot1\cdot5\cdot4\cdot3}{5^6}=\frac{75\cdot5\cdot32}{5^6}=\frac{96}{125}.$$

-
I don't believe this is the correct distribution. We don't have the stipulation that there must be a vacation day taken by some worker each day. –  mach Dec 9 '13 at 7:34
@mach I changed my answer in response to your comment; I think it depends on how the question is interpreted. –  user84413 Dec 23 '13 at 22:47