Combination with limited repetition: What is the probability of drawing a desired card in a $6$-card hand from a deck of $40$ cards?

53 Views Asked by At

Suppose you're playing a trading card game consisting of $40$ cards. In such a deck, you may only have at most $3$ copies of any given card. Some cards are especially powerful and are restricted by the publishers, meaning a player can have at most $2$ copies or even just $1$ copy of that card in their entire deck. Thus, it's always the case that any card appearing in a deck has a quantity of $1 \leq x_i \leq 3$.

Problem: You know your deck consists of $20$ distinct cards whose quantities sum to exactly $40$. One of those cards is very powerful and is limited to just one copy, so you want to have it right at the start of the game. Again, the rest of the cards are known to have a quantity of $1 \leq x_i \leq 3$. What is the probability of drawing the target card in this $6$-card hand?


If there were no repetition at all in the deck, the answer would be $\frac{39 \choose 5}{40 \choose 6} = 0.15$: the number of ways to choose $\frac{5}{6}$ of the cards to not be the desired one, divided by the number of ways to choose a $6$-card hand from a deck of $40$.

But our problem is a little more complicated because there is some repetition, and repeated cards are indistinguishable from each other. I can maybe create an equation like this in an attempt to use stars and bars:

$$ x_1 + x_2 + x_3 + ... + x_{19} + 1 = 40 $$

In fact, I'm not so sure about this approach. Should it be $x_{19}$ or $x_{6}$? Six is the total number of cards in my hand, and $19+1 = 20$ is the number of distinct cards in the deck.

Where the $+1$ is the target card with a known quantity of one, and all other cards are $1 \leq x_i \leq 3$. So then:

$$ x_1 + x_2 + x_3 + ... + x_{19} = 39 $$

I know I can apply the usual stars-and-bars technique like so:

$$ x_i \geq 1 \implies x_i - 1 \geq 0 $$

Let $x_i' = x_i - 1$, so that $x_i = x_i' + 1$.

Substituting:

$$ x_1' + 1 + x_2' + 1 + x_3' + 1 + ... + x_{19}' + 1 = 39 \\ x_1' + x_2' + x_3' + ... + x_{19}' + 20 = 39 \\ x_1' + x_2' + x_3' + ... + x_{19}' = 19 $$

But how do we factor in the upper limit of $3$ for each card? This equation is one where $3 \geq x_i' \geq 0$, not where $x_i' \geq 0$ unbounded. If I could ignore the upper limit, I would proceed with the usual stars-and-bars method, but that would imply that I could have $4$, $5$, or any more copies of a given card.