Card combinatorics problem

285 Views Asked by At

Suppose we have a standart deck of cards. It is fixed and can have maximally 52 cards, but may be less. Also we have several subsets of this deck, each subset consist either of all cards of the same rank (e.g. 4s, 4d, 4h, 4c) or all cards of the same suit. We need to take some minimal number of cards from each of these subsets. The subsets are fixed, ie ranks and suits which are requested are fixed. Denote these subsets $A_1$, $A_2$, ..., $A_k$ and the minimal number of cards which is requested from these subsets $a_1$, $a_2$, ..., $a_k$.

The process is the following: $n$ cards from the deck are dealed. We need to know the probability that in these $n$ cards we will have not less than $a$ cards from $A$, not less than $b$ cards from $B$, and etc. So the question is: what is number of variants to deal $n$ cards from the deck, in which we have not less than $a$ cards from $A$, not less than $b$ cards from $B$, and etc. ?

I'll try to report my progress. Let's first consider that subsets don't intersect. In this case the formula for variants number is $$ N = \sum_{c_1+c_2+...+c_k \le n,\;c_j\ge a_j} \binom{|A_1|}{c_1}\binom{|A_2|}{c_2}...\binom{|A_k|}{c_k}\binom{d-\sum_{i=1}^k|A_i|}{n - \sum_{i=1}^k c_i}. $$ Here $d$ is the number of cards in the deck, $|A_i|$ - number of cards in the $i$-th set, and $c_i$ is the numbers of cards which we take from the set $A_i$. So we sum over all possible distributions of $n$ cards in subsets, taking the remaing cards from the rest of the deck.

But there are intersetions between sets: if one set is a rank set, e.g. rank 4, and other is a suit set, e.g. spades, then card 4s belongs to both sets. In this case formula above gives overvalued result. If sets $A_i$ and $A_j$ have common card $x$, then we count several variants where card $x$ was taken twice: once as a member of the set $A_i$ and once as a member of the set $A_j$.

So, we need to subtract these odd counted variants. Let's consider the case of two sets. Then we can subtract in such a way: $$ N = \sum_{c_1+c_2\le n,\;c_j\ge a_j} \binom{|A_1|}{c_1}\binom{|A_2|}{c_2}\binom{d-|A_1|-|A_2| + 1}{n - c_1 - c_2} - \binom{|A_1| - 1}{c_1 - 1}\binom{|A_2| - 1}{c_2 - 1}\binom{d-|A_1|-|A_2| + 1}{n - c_1 - c_2}. $$ The second term which is subtracted is the number of odd combinations, when we take one card twice. This idea can be generalized on the case of several sets (and, so, more then one intersections between sets), using Inclusion-Exclusion formula.

However, the result is still wrong. For example in the case $n = 4, \; A_1 = \{a, b, c\}, \; A_2 = \{b, d\}, \; a_1 = 2, \; a_2 = 1$ and $d = 10$ using the formula we get $N=26$ and the correct answer is $N=25$. The problem is that we calculate combination $\{a, b, c, d\}$ twice: first time when we take $3$ cards from $A_1$ and $1$ card from $A_2$ and second time when we take $2$ cards from $A_1$ and $2$ card from $A_2$. By now I don't know how to treat this kind of inaccuracy in general case.