Combinatorics problem - choosing $6$ cards out of $32$-card deck so that there are exactly three different suits (Inclusion-Exclusion)

Question

Suppose we have a deck of $32$ cards with $8$ cards of each of the four suits. In how ways we can choose six cards such that there are cards of exactly three different suits among the chosen cards?

I believe inclusion-exclusion principle is the way to solve it, where we first count the number of total ways to choose $6$ cards out of $32$ (which is $\binom{32}{6}$), then exclude the number of combinations where exactly two of the suits are missing (which is $\binom{4}{2}\binom{16}{6}$) and then by inclusion-exclusion formula add the combinations where all three suits are missing (which is $\binom{4}{3}\binom{8}{6}$). The number of combinations of all $4$ suits missing is, of course, zero.

My question is - where is my logic incorrect? I know it is, but can't seem to spot the error.

Answer 1

There are two issues here. The first is that the standard inclusion-exclusion formula assumes you start by subtracting events where at least one thing is missing, so that everything where two are missing is counted twice, three missing counted three times, etc, and that is what means you only have to add or subtract once, and which you do alternates.

Here you start by subtracting things where two are missing. This means that you have subtracted everything with three missing three times (from three suits you can choose a pair in three ways), and so you need to add on twice the number of ways to have three suits missing. (If it was a possible situation, you'd then need to subtract three times the number of ways to have four missing: you would have so far subtracted these configurations six times and added them eight times.)

The second problem is that you haven't accounted for all the situations where all four suits are present. So after making the change from the previous paragraph, what you have calculated is the number of ways to have at least three suits among the chosen cards.

Answer 2

It is better to count the hands that are void in exactly one suit.

If we try $\binom{24}6 - \binom4 2 \binom{16}6 + \binom4 3\binom8 6$, we will get the number of hands void in at least one void suit, since we are only subtracting the overcount of the multiply void ones, whereas to get the number with exactly one void suit, we need to subtract the entire count of the multiply void ones

This number is 4 times the number of hands void in,say,$\;$$ \spadesuit$ which can be combined in $3$ ways to form hands void in $2$ suits, and eliminate the over count by adding the $3$ ways in which the hand can be void in $3$ suits in combination with the $\spadesuit$ to give us $4[\binom{24}6 - 3\binom{16}6 +3\binom8 6]$

Answer 3

There are four qualities that hands may have. There are hands that miss clubs, hands that have no hearts, hands without spades and hands without diamonds.

The situation is tricky because the binomial coefficients intervene in a double way. To reveal this let us use $N(x)$ and $E(x)$ the generating functions for the "hands having at least x qualities" and "hands having exactly x qualities".

Shortly, P.I.E says that $N(x)= E(x+1)$

Here

$N(x) = \binom 4 3 \binom 8 6 x^3 + \binom 4 2 \binom {16} 6 x^2 + \binom 4 1 \binom {24} 6x + \binom 4 0 \binom {32} 6$

$N(x) =112x^3 + 48048x^2 + 538384x + 906192$

$E(x) = N(x-1) = 12x^3 + 47712x^2 + 442624x + 415744$

As one may see, $442624$, the desired number, is

$442664 = \color {red}{\binom 3 1 }\binom 4 3 \binom 8 6 - \color{red}{\binom 2 1 } \binom 4 2 \binom {16} 6 + \color{red}{\binom 1 1 } \binom 4 1 \binom {24} 6$

Suppose now we have a 3-color deck of 24 cards and we are interested in all-color hands. Again,

$N(x) = \binom 3 2 \binom 8 6 x^2 + \binom 3 1 \binom {16} 6 x + \binom 3 0 \binom {24} 6 $

$N(x) =84x^2 + 24024x + 134596$

$E(x) = N(x-1) = 84x^2 + 23846x + 110656$

$110656 = \color {red}{\binom 2 0 }\binom 3 2 \binom 8 6 - \color{red}{\binom 1 0 } \binom 3 1 \binom {16} 6 + \color{red}{\binom 0 0 } \binom 3 0 \binom {24} 6$

Again, as we may see, $442624 = 4\times 110656$

=====

:) And do not be afraid of "generating functions"; they are neither generating nor functions but just mnemonical expressions that fit and help to shorten the writing.