Calculating number of variants of variants with a generating function?

Question

Imagine you are choosing 2 cards each from different 2 different suits (13 cards in each) and the ordering of suits does not matter. The goal is to calculate the number of possible combinations of cards. The "absolute value" of the suit doesn't matter, e.g. 9♣10♣J♠Q♠ is the same as 9♠10♠J♣Q♣. But neither are the same as 9♠J♠10♣Q♣ (the 9 and 10 are no longer the same suit).

For single suit of $x$ cards, we have $13 \choose x$ variants. We now need to choose without ordering and with replacement one variant for each of this variant. Using the multiset coefficient, we get ${{{13 \choose{x}} + 2 - 1}\choose 2} = 3081$ (details).

I would like to arrive at the same answer using a generating function. Naively, I'd expect the coefficient for $x^4$ of $(1+x+x^2)^{13}$ to be the number of combinations -- we're constraining each of the 13 ranks to be chosen 0-2 times and choosing 4 cards. But this evaluates to 1651.

What causes the difference? How could the generating function be changed to be correct?

The goal of expressing this using a generating function is to find a solution for the case where there are a differing number of cards per suit.

Answer 1

With the hints from JMoravitz and Philipp, I think I have a solution -- albeit an ugly one.

Let's take the example where we are choosing 2 cards from 2 suits. One suit has 10 cards in it. The other has 13 cards. We can represent the number of combinations as:

$(1+x+x^2)^{\binom{10}{2}}*(1+x)^{\binom{13}{2}- \binom{10}{2}}$

The number of combinations is the coefficient of $x^2$.

When both suits have the same number of cards, this solution collapses to the first term -- which is equivalent to the multi-set coefficient approach. Each of the variants ($\binom{10}{2}$) for each suit can be chosen 0, 1, or 2 times.

If there are a different number of cards, we calculate the "extra" variants that are only possible in the suit with more cards. These variants can only be chosen 0 or 1 time.

I believe this should generalize to any number of suits. But a more elegant solution is welcome.

Answer 2

Your generating function undercounts the combinations because it does not account for the need to choose these cards from two different suits. It includes the combinations where all four cards could be from the same suit or from more than two suits which is not allowed in your problem statement.

So ideally to choose 2 cards from each of two suits the combined generating function would be $((1+x+x^2)^{13})^2$. The coefficient of $x^4$ is 23075 there. But since this counts each combination twice, once for each suit, we'd normally divide by 2. Which gives us 11537.5 which is meaningless. So unfortunately using a generating function here is not possible as far as I can tell.

Using the multiset coefficient method seems like the way to go.

When to use generating functions:

• each choice is independent
• the constrains are additive or multiplicative

When not to use generating functions:

• indistinguishable categories
• specific limitations on the choices