# non-routine application of inclusion-exclusion

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.

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....

-
There IS (what you call) a resolution of the issue over there. – Did Jan 13 '12 at 7:16
@Didier Piau : Wow ! Getting a lot of flak ! I posted a revised q so as to highlight the central issue that is bothering me. Ok, let me see if i can convince people that there IS an issue. Maybe in an hour or so. – true blue anil Jan 13 '12 at 9:03
Why the downvotes, people? This seems like a legitimate source of confusion -- with some handwaving either explanation seems plausible. And it's up to us not only to explain why the correct one is correct but also why the wrong one is wrong. – Scaramouche Jan 13 '12 at 10:22
I suspect the downvotes were given because the question gives no indication whatsoever how one might arrive at the "non-routine" formula, and it shares this non-feature with the previous one it refers to -- as long as the OP doesn't provide a reason why one might think that that formula is correct, there's no question here to answer; all one can say is that it isn't correct because the other one is correct. @Scaramouche: We wrote our comments simultaneously. If you see how the other formula could be plausible, I'd be interested to hear. (Still it would have been the OP's task to explain that.) – joriki Jan 13 '12 at 10:23
Isn't the OP's non-routine formula the correct one in this case? For instance, look how many times are we counting hands void in C&D. Once for all hands void in C, and again for all hands void in D, but we should in actuality count it 0 times since this hand only has 2 suits, not 3?? Not too sure here but I think this logic is right. – Scaramouche Jan 13 '12 at 10:31

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} .}$$

-
Well done! This is a great lesson in groupthink. I had a vague feeling that perhaps the OP might be right but then convinced myself of the answer given by André and confirmed by Didier. What André calculated is in fact the number of hands with at least one void. – joriki Jan 13 '12 at 12:06

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.

-
+1 Nice to know! I wonder how to understand the formula for the probability? Are there references that explain it? – Tim Jan 13 '12 at 16:47
+1. Nice answer. – Did Jan 13 '12 at 18:12
@DidierPiau Thanks! – Byron Schmuland Jan 13 '12 at 18:30