non-routine application of inclusion-exclusion

Question

What are the circumstances when inclusion-exclusion can't be routinely applied, and some adjustments have to be made ?

This question arises from a problem of finding the probability of getting a bridge hand void in exactly one suit, ie consisting of exactly 3 suits ?

Leaving aside the denominator of C(52,13) for the nonce, one would have thought that the # of favorable ways = C(4,1)*C(39,13) - C(4,2)*C(26,13) + C(4,3)*C(13,13)

but instead it is C(4,1)*C(39,13) - 2*C(4,2)*C(26,13) + 3*C(4,3)*C(13,13).

The original q, A bridge hand void in one suit led to the predictable (incorrect) answer, w/o resolution of the issue.

Addendum:

Since there is some skepticism about the "non-routine" formula, i have worked out a solution by another (rather laborious method)

suitwise cards # of ways

11-1-1-0 ..... 158184

10-2-1-0 .... 6960096

9-3-1-0 .... 63800880

9-2-2-0 .... 52200720

8-4-1-0 ... 287103960

8-3-2-0 ... 689049504

7-5-1-0 ... 689049504

7-4-2-0 .. 2296831680

7-3-3-0 .. 1684343232

6-6-1-0 ... 459366336

6-5-2-0 .. 4134297024

6-4-3-0 .. 8421716160

5-5-3-0 .. 5684658408

5-4-4-0 .. 7895358900

......... 32364894588

This tallies exactly with the "non-routine" application of inclusion-exclusion, whereas the "routine" application yields a figure of 32427298180.

Maybe someone can help....

Answer 1

I would have to agree with you on this one; your previous answer seems to be incorrect.

Let $S_1$ denote the set of all bridge hands void in Clubs, and $S_2$ void in diamonds, $S_3$ void in hearts, $S_4$ void in spades.

The set you want to count is $S := \{ x | x $ is in exactly one of $S_1, \ldots, S_4 \}$. Note that this is not equal to $S_1 \cup S_2 \cup S_3 \cup S_4$, ($S_1 \cap S_2 \not \subset S$) and thus we cannot use direct PIE.

We use the same technique, though. We start as usual, $$ |S| = |S_1| + |S_2| + |S_3| + |S_4| \cdots$$ Here we have overcounted the members of the sets of the form $S_i \cap S_j$ twice each, so $$|S| = \sum_i |S_i| - 2 \sum_{i\neq j} |S_i \cap S_j| \cdots $$ Now we have counted the members of the sets of the form $S_i \cap S_j \cap S_k$ a total of $$ \binom 3 1 - 2 \binom 3 2 = -3$$ times so we need to add them in: $$ |S| = \sum_i |S_i| - 2 \sum_{i \neq j} |S_i \cap S_j| + 3 \sum_{i \neq j \neq k} |S_i \cap S_j \cap S_k| \cdots $$ It is easy to continue the pattern further, though we do not need it. The final answer then, as you stated, is $$ \fbox {$ \binom 4 1 \binom {39}{13} - 2 \binom 4 2 \binom{26}{13} + 3 \binom 4 3 \binom{13}{13} $.}$$

Answer 2

I often find the following version of inclusion-exclusion to be useful:

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 $$p(k)=\sum_i (-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.

It is the factor $i\choose k$ that makes the application "non-routine", and (with $k=1$) this explains the numbers 1, 2, and 3 in Scaramouche's answer.

---

Added: Here's a proof of the formula. Let $X$ be the random variable that counts the number of events $(A_j)$ that occur. Then $$\mathbb{E}\left[{X\choose k}\right]=\sum_i {i\choose k}\, \mathbb{P}(X=i).$$ Now apply binomial inversion to obtain $$\mathbb{P}(X=k)=\sum_i (-1)^{i-k}{i\choose k} \mathbb{E}\left[{X\choose i}\right].$$

Reference: Section 2.5 of Problems and Snapshots from the World of Probability by Gunnar Blom, Lars Holst, and Dennis Sandell.