Or at least, it can involve dice, depending on how you look at it.
Here’s the basic situation:
If I roll N S-sided dice (where N>=S), what is the probability that every face value (from 1 to S, of course) will be represented at least once? Preferably, I’d like to be able to actually count (but nut enumerate :eek:) the number of ways that this can happen for arbitrary values of N and S.
Another way of looking at the problem is the happy meal dilemma. Suppose that a national burger chain is giving out a free toy with each kid’s meal. There are S different toys in the set. Each time that you buy a kid’s meal, the particular toy that you receive is selected at random (that is, with equal probability) from the set of toys. Now suppose that I have a bratty kid that insists on not just getting a particular toy, but on getting all of the toys. If I purchase N kid’s meals, what is the probability that I will have obtained (at least one of) every toy?
And now for the “weird” interpretation which is probably more familiar to math students:
I have S distinguishable objects (ex. numbered, labeled balls) and N distinguishable bins. How many ways can I place the balls into the bins such that no bin is empty?
This is a deceptively simple-sounding problem, probably because it’s so similar to a variety of very easy to solve problems. But every attempt I’ve made to solve it quickly turns into an epic quagmire of combinatorics.
Here’s the general train of my thought so far. For the sake of example, let’s say that I’m rolling 12 normal dice (6-sided). I want to know how many of the possible outcomes will contain at least one 1, one 2, one 3, …, and one 6.
Solving for the number of ways that this can happen without respect to order is surprisingly simple. This is really the same problem as: I have 12 (unnumbered) ping-pong balls and 6 numbered boxes. How many ways can I place the ping-pong balls into the boxes, leaving no empty boxes? Which, in turn, can be conceptualized as laying out the ping-pong balls in a line, and then partitioning the line into 6 parts using 5 dividers. There are 11 places that I can put each of the 5 dividers. Therefore, there are C(11,5) = 462 ways of doing this. However, a “way” in this case doesn’t respect which balls go into which boxes, just the total number of balls in each numbered box. This is great if you want to know how many distributions there are for rolling N S-sided dice, but it doesn’t give you the number of ways that each distribution can occur, which you would need to know to solve this problem.
Similarly, it’s easy to determine the number of ways that we can place N distinguishable objects into S distinguishable boxes, where the exact number of objects in each of the bins is known. That is, if I have an exact distribution in mind – like 1 one, 4 twos, 2 threes, 2 fours, 1 five, and 2 sixes – I can work out the number of ways for that happen pretty easily. In the example just given, this is simply:
12! / (1! * 4! * 2! * 2! * 1! * 2!) = 2,494,800
Which is about 0.115% of all possible outcomes for rolling 12 6-sided dice.
I’ve been trying to figure out some way to fuse these two tools together into something that I can leverage against this beast. That is, to somehow count the number of distributions, and from there, count the number of permutations for each distribution. But it just gets way too complex for anything but the smallest values of S and N. Certainly nothing I’ve come up with will provide a general approach for solving this for any arbitrary value of S and N.
Have I missed something really obvious? It seems like such a simple-sounding problem should have a simple solution.