Distinct terms in multinomial expansion

Question

How many distinct terms are obtained after combining all terms in the expansion of $$(1+x^3+x^5)^{20}?$$

I know the multinomial expansion, but I am not able to use that to find the distinct terms that will be obtained in this expansion. I know that the powers of $x$ will be of the form $P=3b+5c$ where $a+b+c=20$. But what after that?

Answer 1

You can reach any integer in $[5n,5n+4]$ via $$\begin{align}5n&=5n+3\cdot0\\ 5n+1&=5(n-1)+3\cdot2\\ 5n+2&=5(n-2)+3\cdot4\\ 5n+3&=5n+3\cdot1\\ 5n+4&=5(n-1)+3\cdot3\end{align}$$ So the only integers in $[0,100]$ that you miss are a few exceptions. $1$, $2$, $4$, and $7$ at the beginning but the after $10$ all numbers are reachable. At the end we can't hit $99=5\cdot18+3\cdot3$ nor $97=5\cdot17+3\cdot4$ but everything below is reachable. So the answer is $100+1-6=95$. Sanity check:

% powers.m

P = [1 0 1 0 0 1];
Q = [1];
for k = 1:20,
    Q = conv(Q,P);
end
count = sum(sign(Q))

Output:

>> powers

count =

    95

Answer 2

You can trade 5 factors of $x^3$ for 3 of $x^5$ and a couple $1$'s. So all distinct powers appearing in the product can be written as $x^{5n+3m}$ for $m=0,1,2,3,4$. Conversely, every such monomial will appear in the product, provided $n+m\leq 20$.$^1$

$n$ ranges from $0$ to $20$. For $n<17$ there is no constraint on $m$, which means there are $5$ possibilities for each such $n$. For $n\geq 17$, the constraint $m\leq 20-n$ limits the number of options to $4,3,2,1$ for $n=17,18,19,20$, respectively.

So the total number of terms is $17\times 5 + 4+3+2+1 = 95$.

[An alternative way to derive this result is with the inclusion-exclusion formula.]

---

Footnote:

1. For $n+m\leq 20$ there are clearly many terms $\propto x^{5n +3m}$ in the expansion, coming from choosing $n$ of the $x^5$ terms and $m$ of the $x^3$ terms. You might worry that they could all cancel, but this can't happen as they all have positive coefficients. So there must be a non-zero term in the product $\propto x^{5n+3m}$.