Title is a bit verbose so here's a scenario: Suppose 4 friends go out to a restaurant, and each of them will order 3 items from a total list of 9 items. Each item ordered by a single person is different. If each person's selection of items is completely random, what is the probability that between the 4 friends, all 9 items on the menu are sampled at least once?
This type of problem would be simmed pretty easily, but I am very interested in the theoretical method that would be used to arrive at the answer.
Here's what I think so far: If each person has (9 choose 3) item combinations (orders), then the total number of order combinations should be ((9 choose 3) ^ 4) / (4!) (since we don't care about who orders what, just that all items are covered). So all that's left is to quantify those order combinations in which every item is covered, and then divide by that total. However, this is where I'm stuck.
It has occurred to me that one way to solve this would be to just add up all of the possible ways for the scenario to succeed. If the items are numbered 1-9 and each {} represents an order, this would look like: P({1,2,3}, {1,2,3}, {4,5,6}, {7,8,9}) + P({1,2,3},{3,4,5},{5,6,7},{7,8,9}) + ... But that type of breakdown seems like a nightmare especially at higher numbers. It feels like there should be a way to make clever use of a choose function for a relatively neat solution.
Thanks for taking the time to read this, and I appreciate any help that may be offered toward finding a solution.
Edit: After mulling this over, I think this can actually be solved with just straight probability without even worrying about the # of combinations. The probability that all items are covered would be 1 - the sum of 1 item, 2 items... 6 items not covered = 1 - Sum(i = 1 to i = 6) {((9-i)(8-i)(7-i)/(9x8x7))^4}. Doing that yields 76.8909%, which seems like a reasonable outcome (I haven't checked this for correctness).
Even if the above approach works, I would be interested in knowing if there are any clever ways to quantify the number of combinations where every item is covered. Thanks!