Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm working on a card game, which uses a non-standard deck of cards. Since I'm still tweaking the layout of the deck, I've been using variables as follows:

Hand size: $H$
Number of suits: $S$
Number of ranks: $R$
Number of copies of each card: $C$

Thus, the total number of unique cards in the deck is $S*R$, and the absolute total number of cards in the deck is $S*R*C$.

Since there are duplicates for each card, I'm trying to find the number of unique hands of size $H$ that are possible for given $S$, $R$, $C$, and $H$. If I'm remembering correctly, ${S*R*C\choose H}$ would over count the number of unique hands in this case.

How would I handle this calculation with duplicate cards?

EDIT: As an aside, how would calculations of unique number of winning hands be different with duplicate cards? I'm thinking of having general types of winning hands, such as $N$-flushes, $N$-straights, $N$-of-a-kinds, etc (restricted to $1 \le N \le H$, naturally).

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

Number the unique cards $1$ through $RS$. Then you’re asking for the number of solutions of $$x_1+x_2+\ldots+x_{RS}=H\tag{1}$$ in non-negative integers, subject to the restriction that each $x_k\le C$. (In other words, for a given solution to $(1)$, $x_k$ is the number of copies of card $k$ the hand.) Without the restriction this would be a straightforward stars and bars problem, and the answer would be $$\binom{H+RS-1}{RS-1}=\binom{H+RS-1}H\;.$$ Unfortunately, the restriction eliminates many of these naïve solutions, and an inclusion-exclusion calculation is needed to take it into account. The result is that the number of distinct hands is

$$\sum_i(-1)^i\binom{RS}i\binom{H+RS-1-i(C+1)}{RS-1}\;.\tag{2}$$

To the best of my knowledge there is no nice closed form for this.

(See also this essentially identical question. The answer by true blue anil gives an indication of how $(2)$ is arrived at.)

For the question about winning hands, you probably want to take into account the number of ways in which a given winning hand may be made. For an $H$-card flush, for instance, you can have any $H$ cards from any of the $S$ suits, and each suit effectively has $CR$ cards, so there are $S\binom{CR}H$ $H$-card flushes, all equally likely. The fact that some of the cards may be identical doesn’t affect this. Similarly, in counting straights you effectively have $CS$ cards of each rank.

share|improve this answer
    
Thanks Brian, this looks very promising. I'm assuming $i$ in the summation above is from $0$ to $RS$? –  Mark LeMoine May 17 '12 at 23:27
    
@Mark: It may stop short of $RS$: you don’t want $H+RS-1-i(C+1)$ to be negative. –  Brian M. Scott May 17 '12 at 23:42
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.