1
$\begingroup$

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

  • 0
    @joriki: OK. $ $2012-01-13

2 Answers 2

4

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

  • 0
    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.2012-01-13
5

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.

  • 0
    @DidierPiau Thanks!2012-01-13