Inclusion-Exclusion confusion: Meeting exactly one friend in lunch time during a semester

Question

From Trotter's Combinatorics Textbook, I was working on this problem from his Inclusion-Exclusion Chapter:

A graduate student eats lunch in the campus food court every Tuesday over the course of a $15$ week semester. [They are] joined each week by some subset of a group of six friends from across campus. Over the course of a semester, [they] ate lunch with each friend 11 times, each pair 9 times, and each triple 6 times. [They] ate lunch with each group of four friends 4 times and each group of five friends 4 times. All seven of them ate lunch together only once that semester. Did the graduate student ever eat lunch alone? If so, how many times?

The solution mainly involves making your sets $A_{i}$ as the set of weeks he ate with friend $i$, and doing inclusion-exclusion from there.

(See Chapter 7 Solutions, Question 9: https://trotter.math.gatech.edu/math-3012/toppage.html)

Now I tried to answer my own follow-up question of how many days he eat with exactly 1 friend.

Since I know that $|A_{1} \cup \dots \cup A_{6}| = 14$, I could just try to do:

$|A_{1} \cup \dots \cup A_{6}| - |(A_{1} \cap A_{2}) \cup \dots \cup (A_{5} \cap A_{6})|$

Now the formula for $|(A_{1} \cap A_{2}) \cup \dots \cup (A_{5} \cap A_{6})|$ I couldn't find online or in the textbooks, so I tried to just count it out myself and noticed a pattern that I think generalizes:

If I add up all the sets that are intersections of 2 friends, I've overcounted the sets that are intersections of 3 friends ${3 \choose 2} = 3$ times, so I have to subtract those sets and their quantities 2 times for them to be counted exactly once! Then for the sets 4-friend-intersections, I first counted them ${4 \choose 2}$ times, then subtracted them $2 \cdot {4 \choose 3}$ times, hence they've been counted $ 6 - 8 = -2$ times, so I have to add those sets and their quantities 3 times.

You continue this logic and you get the coefficients should be +1, -2, +3, -4, +5. In particular I mean that:

$$ |(A_{1} \cap A_{2}) \cup \dots \cup (A_{5} \cap A_{6})| = \sum|(A_{i} \cap A_{j})| - 2 \cdot \sum |(A_{i} \cap A_{j} \cap A_{k})| + 3 \cdot \sum |(A_{i} \cap A_{j} \cap A_{k} \cap A_{l})| - 4 \cdot \sum |(A_{i} \cap A_{j} \cap A_{k} \cap A_{l} \cap A_{m})| + 5 \cdot \sum |(A_{i} \cap A_{j} \cap A_{k} \cap A_{l} \cap A_{m} \cap A_{n})|$$

But when I try plugging in the numbers I get -16:

${6 \choose 2}9 - 2 {6 \choose 3} 6 + 3 {6 \choose 4} 4 - 4 {6 \choose 5} 4 + 5 {6 \choose 6} 1 = -16$

which is weird since I use this same method for this problem (Combinations' Problem) and I get 7 and hence 13 - 7 = 6 times they ate with exactly 1 friend alone, which is correct.

Am I missing something here? I've been think about this problem for a while now but am really stuck. Kindly please help here.

Answer 1

The following is the extension of the inclusion-exclusion principle that you were looking for:

If $(A_j)_{j\in J}$ is a finite or countable collection of events, then the probability that exactly $k$ of these events occur is $$\color{blue}{p(k)=\sum_{i\ge k} (-1)^{i-k}{i\choose k}\sum \mathbb{P}\left(\bigcap_{j\in J(i)}\, A_j\right)}$$ where the sum runs over all subsets $J(i)$ of the index set with $i$ elements.

Hence, for $k=1$ the correct formula is

$$ \color{blue}{\sum_{i} |A_i| - 2 \sum_{i \neq j} |A_i \cap A_j| + 3 \sum_{i \neq j \neq k} |A_i \cap A_j \cap A_k| \cdots} $$

You may see here for more details on how the above special case for $k=1$ is derived.

For your problem this gives:

$${6 \choose 1}11-2{6 \choose 2}9 + 3 {6 \choose 3} 6 - 4 {6 \choose 4} 4 + 5 {6 \choose 5} 4 - 6 {6 \choose 6} 1 = 30,$$

which is greater than $14$ (meeting at least one friend). This means that the given numbers $11, 9, 6,4, 4, 1$ are not properly selected. In fact, your method also gives the same answer $14-(-16)=30,$ but $-16$ is not acceptable as the cardinal of a set.

---

To make sure that the given numbers are incorrect consider the following inequality [1]:

$$\fbox{$\sum_{i=1}^n \sum_{j=1}^nP(A_i \cap A_j) \geq \Bigl( \sum_{i=1}^n P(A_i) \Bigr)^2.$}$$

For the given numbers, we have $$\sum_{i=1}^n P(A_i)=\frac{6\times 11}{15}=4.4$$ $$\sum_{i=1}^n \sum_{j=1}^nP(A_i \cap A_j)=\frac{6\times 11+2\binom{6}{2}9}{15}=8,$$ so the above inequality does not hold: $$8 \color{red}{\ngeq} (4.4)^2=19.36.$$