1
$\begingroup$

I recently had the following question, which I answered incorrectly, in a combinatorics exam:

How many ways are there to put 8 balls in 9 holes $H_1, ..., H_9$ if the balls are all different and only the holes $H_1, H_2, H_3, H_4$ are empty?

Apparently, the solution is:

$$5!S(8,5)$$

Where $S(8,5)$ is the Stirling number. In effect, the solution is the number of surjective functions from the set of cardinality 8 to the set of cardinality 5.

Is someone able to explain this solution to me? From my understanding, if we know that $H_1, H_2, H_3, H_4$ are all empty, it's simply a matter of assigning 8 balls to the 4 holes. The question doesn't state anything about a hole containing at least one ball.

$\endgroup$
8
  • $\begingroup$ I'm confused as well. If a hole can contain more than one ball, why does the question say anything about holes previously being empty or not empty? Perhaps because the goal is to count how many configurations of possibly-multiple-balls-in-holes there are - but then, wouldn't we also need to know how many balls are currently in the non-empty holes? On the other hand, if a hole cannot contain more than one ball, why would the exam bother stating the problem with obviously useless information? (Non-obviously useless information would be understandable.) $\endgroup$ Jun 20 '15 at 5:55
  • $\begingroup$ @Zev: The problem is to count the ways to distribute the $8$ balls amongst the $9$ holes in such a way that precisely the first $4$ holes are empty. $\endgroup$ Jun 20 '15 at 5:58
  • $\begingroup$ @Brian: That's an interpretation that explains the given answer, but I'd have to consider it a poorly-worded question if that is the intended meaning. $\endgroup$ Jun 20 '15 at 5:59
  • $\begingroup$ @Zev: It certainly wins no prizes for clarity. $\endgroup$ Jun 20 '15 at 6:01
  • 1
    $\begingroup$ It is not that the question is not clear (my guess that the final "are empty" should be read "are to remain empty" seems right), it is just slightly weird. Why would one want to introduce the first four holes only to then require that they remain unused? It seems like the only reason is to better hide the fact that the phrase "only the holes ..." also requires the other holes not to remain empty. $\endgroup$ Jun 20 '15 at 6:07
1
$\begingroup$

The first four holes are empty, so you're assigning each ball to one of the last five holes. Each of the last five holes is non-empty, so you're choosing a surjection from the set of eight balls to the set consisting of the last five holes. The answer does assume that the balls are distinguishable, as is stated in the question.

$\endgroup$
2
  • $\begingroup$ Oooh - I see now. The way I interpreted the question was the the balls could not be put in the last 5 holes, only the first 4 were available. This answer makes sense to me now. I still think this is a poorly worded question. $\endgroup$
    – rheotron
    Jun 20 '15 at 6:00
  • $\begingroup$ @rheotron: I agree with you. $\endgroup$ Jun 20 '15 at 6:02

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.