[Math] Use a generating function to count the number of combinations with limited repetition

combinatoricsdiscrete mathematicsgenerating-functions

What's the number of multisets of size five of $\{A, B, C, D, E\}$ if some letter occurs at least three times?

Using PIE we see the answer to this problem is $75.$ Though, I am not quite sure how to set up a generating function here.

I do know that

The product $(1 + X)(1 + X+ X^2)(1 + X + X^2 + X^3)$ is called the generating
function for counting combinations from a three-element set, when one element
can be selected at most once, another at most twice, and the third at most three
times. The coefficient of $X^k$ in the product is equal to the number of $k$-element combinations that satisfy these conditions.

Using the quote above as a guide I tried $(1 + X)^2(1 + X^3 + X^4 + X^5),$ but that seems wrong. What am I doing wrong here? How can I fix that? Thanks.

Best Answer

Because order doesn't matter, you can create a combination by choosing the number of $A$s, then choosing the number of $B$s, etc.

The act of choosing between $p$ and $q$ of the same letter is represented by the factor $(x^p+x^{p+1}+\ldots+x^q)$. For example, choosing between $0$ and $2$ $B$s is represented by $1+x+x^2$.

If you can choose any number of a particular letter, the factor in the g.f. is $\frac1{1-x}$. For two letters, this becomes $\frac1{(1-x)^2}$.

Now let $f(x)$ be the g.f. representing the choice of any number of each of the five letters.

Then let $g(x)$ be the g.f. representing the choice of $0,1,$ or $2$ of each of the five letters.

Then the needed g.f. is $f(x)-g(x)$.


If you absolutely need to find a coefficient by hand, use $$\frac1{(1-x)^n}=\sum_{i=0}^\infty\binom{n-1+i}{i}x^i$$and $$(1+x+x^2)^n=\sum_{i+j+k=n}\binom{n}{i,j,k}x^{j+2k}$$ In that last one, the coefficient of any specific term $x^p$ is a sum of several multinomials.

Related Question