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

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!

• For what it's worth, I started to leave an answer, but then discarded it, because the math is so ugly. A very crude approach is to work the problem iteratively, going from Person-1 to Person-2 to ... to Person-N. If you assume (without loss of generality) that in your stated problem, Person-1 chose items $\{1,2,3\}$ from $\{1,\cdots,9\}$, then there will be $r$ elements in the intersection between Person-2's choices and Person-1's choices, with $r \in \{0,1,2,3\}.$ ...see next comment Aug 25, 2021 at 4:08
• Then the probability of a specific value of $r$ occurring will be $$\frac{\binom{3}{r} \times \binom{9-3}{3-r}}{\binom{9}{3}}.$$ Then, you explore each of the possibilities of there now being $(6-r)$ distinct items selected, and you move on to Person-3. ... Told you this was ugly. My knowledge of Probability Theory is way too inadequate to even guess whether there is some elegant simplification to all of this. Aug 25, 2021 at 4:13
• To illustrate continuing the thought, with Person-3, if there are now $(6-r)$ distinct items chosen, and $s$ is the number of items that Person-3 chose that intersect with these $(6-r)$ distinct items, then for $s \in \{0,1,2,3\}$, the chance of $s$ occurring is $$\frac{\binom{6-r}{s} \times \binom{9 - [6-r]}{3-s}}{\binom{9}{3}}.$$ Aug 25, 2021 at 4:21

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.

• Math Lover, thank you very much for your answer! I have never seen P.I.E. applied like this, and even with my rudimentary understanding of the principle, I can sense how powerful of a tool it can be. Aug 25, 2021 at 23:58
• @HonorableSeddoku you are welcome! Yes it is indeed a powerful tool. Aug 26, 2021 at 0:16