Determining combinations with duplicates - how many different game decks can I build?

Question

I own a game called Ortus Regni. Each player is given a stack of 90 cards comprised of 6 cards each in 15 different patterns. From these 90 cards, you build a game decks of 24 cards. There are no restrictions in how this deck is built. You can use all 6 duplicates of any pattern, or none of a pattern or any other number. The least number of different patterns a game deck can contain is 4 (4 patterns x 6 duplicates each = 24 cards). On the other hand, there are numerous ways to build a 24 card game deck that uses all 15 patterns.

My question is how many different game decks of 24 can be built from the 90 cards? If all cards were different, you could solve this with the simple combination 90 taken 24 at a time. It's the 15 sets of 6 duplicates each that I can't figure out. Order does not matter, so many decks in the simple combination will be equivalent.

Answer 1

Inclusion exclusion for the win!

Let $x_1,x_2,\dots,x_{15}$ be the number of cards chosen from each pattern. Each $x_i$ is a nonnegative integer between $0$ and $6$, and their sum is $24$. We are therefore counting integer solutions to the equation $$ x_1+x_2+\dots+x_{15}=24\\\tag1 x_i\ge0,\\ x_i\le 6. $$ Let us forget the last condition, and instead count solutions to the simpler problem $$ x_1+x_2+\dots+x_{15}=24\\\tag2 x_i\ge0. $$

By "stars and bars," the number of ways to build the deck would be $\binom{24+15-1}{15-1}$. From this, we must subtract the bad solutions where at least one of the variables $x_i$ is more than $6$. For example, when $x_1$ is the bad variable, we get $$ x_1+x_2+\dots+x_{15}=24\\\tag3 x_1\ge7.\\ x_i\ge 0\quad\text{ for all } i\ge 2 $$ Subtracting $7$ from the value of $x_1$, an equivalent problem is $$ x_1+x_2+\dots+x_{15}=17\\\tag{3'} x_i\ge 0\quad\text{ for all } i\ge 1 $$ Again, stars and bars gives an answer of $\binom{17+15-1}{15-1}$. This number must be subtracted for each of the $15$ variables $x_i$, leaving $$ \binom{24+15-1}{15-1}-15\binom{24+15-1}{15-1} $$ But wait! The solutions to $(2)$ with two bad variables where subtracted out twice. We must now count these doubly subtracted variables and add them back in. Then there will be triply bad solutions will need to subtracted out again (I do not want to explain all the details about how inclusions exclusion works, you can read up on this on your own). We can stop at three since it is impossible to have four variables $x_i$ which are more than $6$ while still adding to $24$. The final result is $$ \binom{24+15-1}{15-1}-15\binom{17+15-1}{15-1}+\binom{15}2\binom{10+15-1}{15-1}-\binom{15}3\binom{3+15-1}{15-1} $$

Answer 2

This is a question that can be naturally answered using a computer and the machinery of Generating Functions. Let $a_n$ be the number of ways of building a deck with exactly $n$ cards. Our eventual plan will be to compute the polynomial $$P(x)=\sum_{n=0}^{90} a_n x^n$$ Once we've done this, we can answer your question just by reading off the $x^{24}$ coefficient of this polynomial.

Warm Up 1: Suppose that we only had $1$ pattern instead of $15$ (and still $6$ cards of that pattern). What would $P(x)$ be?

Answer: For each $n$ between $0$ and $6$, there is exactly one way to build an $n$ card deck, since all of our cards are the same. So we have $$P(x)=1+x+x^2+\dots+x^6.$$

Warm Up 2: Suppose we have two patterns with $6$ cards each. Now what is $P(x)$?

Answer 1: (Direct Calculation) For $0 \leq n \leq 6$, there's $n+1$ ways to choose the deck (we could have anywhere between $0$ and $n$ cards of the first pattern). For $7 \leq n \leq 12$, there's $13-n$ ways to choose the deck (we have somewhere between $n-6$ and $6$ cards of the first pattern). So our polynomial is $$P(x)=1+2x+3x^2+4x^3+\dots +7x^6+6x^7+5x^8+\dots +x^{12}$$

It turns out this polynomial factors nicely as $P(x)=(1+x+\dots +x^6)^2$. This is not a coincidence!

Answer 2: I claim that we could have seen $P(x)=(1+x+\dots +x^6)^2$ without doing any calculation. One way to think about it. Imagine multiplying out $$(1+x+\dots+x^6)(1+x+\dots+x^6)$$ We get a bunch of terms of the form (something on left)$\times$(something on right), then combine like terms. You can think of each term of the form $x^a \times x^b$ corresponds to "pick $a$ cards of the first pattern and $b$ cards of the second pattern". Combining like terms then means the $x^n$ coefficient counts all the different ways of getting $n$ cards total.

Effectively, what we're doing in answer $2$ is taking the generating function for each pattern, and multiplying them. We can follow the same pattern for $15$ colors, but now we're multiplying $15$ terms instead of $2$:

$$P(x)=(1+x+x^2+\dots+x^6)^{15}.$$

Now you can use your favorite computer algebra system (e.g. Wolfram Alpha) and get a coefficient of $5,897,438,705$.