Combinatorics question: N people selecting k objects (without replacement) from field of K total objects. Odds all objects are selected?

Question

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!

Answer 1

There are two approaches that I would focus on in my answer -

i) Apply Principle of Inclusion Exclusion (is what I would recommend)

ii) Work case by case

i) Apply P.I.E

Let's find number of different orders where all $9$ dishes are not ordered. That is given by,

$\displaystyle \sum \limits_{i =1}^{6} (-1)^{i+1} {9 \choose i} {9-i \choose 3}^4 = 46700136$

Explanation: ${9 \choose i}$ is the number of ways of choosing $i$ dishes that are not ordered. Also note there are minimum $3$ dishes that get ordered.

So the desired probability is,

$P = \displaystyle 1 - \frac{46700136}{{9 \choose 3}^4} = \frac{125}{2016}$

---

ii) Case by case (I will provide an approach and working of a few cases but will leave the rest to you. It is cumbersome but if you want to practice counting, go for it!)

Note that in total, there are $12$ dish orders. If all $9$ dishes on the menu are served, we have either $1$ dish ordered more than once, $2$ dishes ordered more than once or $3$ dishes ordered more than once.

a) $1$ dish ordered more than once

Then each of them must have $2$ dishes each which are ordered only once. Number of different orders -

$ \displaystyle {9 \choose 1} {8 \choose 2} {6 \choose 2} {4 \choose 2} = 22680$

b) $2$ dishes ordered more than once

Arrangements of non-repeat dishes -
$2~2~2~1 \ $ and $ \ 3~2~1~1$. This leads to number of different orders as,

$\displaystyle {9 \choose 2} {4 \choose 1} {7 \choose 2} {5 \choose 2} {3 \choose 2} \cdot 3 \cdot 2 + {9 \choose 2} \cdot 2 \cdot {4 \choose 2} {7 \choose 3} {4 \choose 2} {2 \choose 1} \cdot 2 = 907200$

c) Similarly for $3$ dishes ordered more than once

Arrangements of non-repeat dishes are $3~3~0~0$, $ \ 3~1~1~1$, $ \ 3~2~1~0$, $ \ 2~2~2~0$ and $ \ 2~2~1~1$

If you do the working, you do get to $2157120$ different orders for (c).

Adding (a), (b) and (c), we finally get to $3087000$ different orders which gives the same probability we obtained using P.I.E.