Find the number of distinct terms in the expansion of
$$\left(x+\frac{1}{x}+\frac{1}{x^2}+x^2\right)^{15}$$ (with respect to powers of $x$)
I saw that the formula for the number of distinct terms (or dissimilar) in a multinomial expansion $(x_1+x_2+x_3+...+x_k)^n$ is $$\binom{n+k-1}{k-1}$$
But applying that here means $$\binom{15+4-1}{4-1}= \binom{18}{3} = 816$$
But the answer says 61.
Is there a difference between the situations for which that formula is meant to be used and that in which I am using??
The Solution (or at least a solution):
Reframed, this question basically amounts to "how many unique sums can you get from $1,2,-1,-2$ if you may use them $15$ times with repetition?" (I show the equivalence later. I do not at all claim this as the only method or the easiest method, it's just the one I came to use.)
You can clearly see that the highest sum is $30$ ($15$ twos) and the lowest is $-30$, giving at maximum $61$ possible sums (all the integers in $[-30,30]$). With some work, you can also see each integer have a valid, corresponding summation.
How so? There's probably a much easier method than this, but here's how I determined it.
Consider some "elementary" units for your summation, every possible way to sum just two of those four numbers. You have possible sums for
With these, consider sums of only $7$ terms made of the numbers $-4,-3,\cdots,3,4$ (analogous to fourteen-term sums of the original fifteen term sum). It should not be difficult to convince you that, with $-4,-3,\cdots,3,4$, we can hit every integer in $[-28,28]$. Why? Consider the highest valid sum, $4+\cdots+4=28$. Replace a $4$ with a $3$ to get one for $27$, and you can continue replacing with $3$'s until you have a sum of seven $3$'s for $21$. You can continue this: replace each of the $3$'s with $2$'s, then $1$'s, then $0$'s, and so on, decrementing the overall sum by $1$ each time. At the end, you have a sum of $-4$'s for $-28$, having hit each intermediate integer.
You can thus claim, with fourteen summands of $-2,-1,1,2$, you can hit every integer in $[-28,28]$. We claim the fourteen summands' conclusion valid, since every $-4,-3,\cdots,3,4$ in our seven-term sums earlier can be replaced with its corresponding sum from our bulleted list (or any other equivalent sum).
Our interest is fifteen-term sums however. This is easy to account for, however. Imagine "shifting" the interval of integers we hit by our new fifteenth summand. For example, if our final summand is $-2$, then the integers we're ensured to hit are $[-30,26]$ - the existence of sums in $[-28,28]$ ensures this. Similarly, if the final summand is $2$ we instead shift the interval of integers hit to $[-26,30]$. Combined, these guarantee the existence of a sum for each integer in $[-30,30]$.
(Or at least I think so. I feel like there's a lurking flaw in my reasoning for some reason. It's probably in part because my method is a little convoluted and I really should go to sleep. I might be imagining things however and just second-guessing myself.)
Thus, every integer in $[-30,30]$ is accounted for by some sum of fifteen terms comprised of $2,1,-1,-2$.
Thus, $61$ is the answer.
Why This Question Is Equivalent:
How does this approach follow?
This might be easier to see in binomial expansions. Consider
$$(a+b)^3 = a^3 + 3a^2b + 3ab^2 + b^3$$
In expanding this and determining the number of terms, you might look at it like this:
$$(a+b)(a+b)(a+b)$$
If you were to write out each term of the expansion individually, without simplifying, you would see
$$\underbrace{aaa}_{a^3}+\underbrace{aab+aba+baa}_{3a^2b}+\underbrace{abb+bab+bba}_{3ab^2}+\underbrace{bbb}_{b^3}$$
Notice that, in expanding $(a+b)^3$, you get every possible way to write a sequence of three $a$'s and $b$'s. There $\binom 3 k$ ways to write a sequence containing $k$ $a$'s specifically, for example. This is because you take one $a$ or one $b$ from each factor of $(a+b)(a+b)(a+b)$.
This holds for higher exponents, and for bigger parentheticals (e.g. trinomials).
Thus, in your expansion of $(x^{-2} + x^{-1} + x + x^2)^{15}$, you have to pick one of the four summands from each of the fifteen factors. You will have as many terms as distinct powers of $x$ as you can make, thus why the number of distinct terms in the expansion is equivalent to the number of distinct sums of fifteen terms of $2,1,-1,-2$ you can make.
Why Your Formula Fails:
The suggested formula assumes the $x_i$'s are all distinct. In your case, they are not: they can combine in ways that distinct terms cannot. This is distinctly noticeable in the case of constants instead of variables: if $a,b$ were constant in the previous expressions, you'd end up with just a single constant at the end, not several different terms. Distinct summands don't permit the additional simplification and elimination of terms.
A less contrived example. Consider the expansions of the two below expressions:
$$(a+b+c)^4 \;\;\;\;\; (x^{-2} + 1 + x^2)^4$$
Insofar as summation formulas go, the two would be equivalent setting $a=x^{-2},b=1,c=x^2$. However, for example, some of the time in the expansion of the latter, you could pick $x^2$ and $x^{-2}$ from a pair of factors, and they would simplify to $1$, or pick $1$ from each of those factors, which also simplifies to $1$. If you were to make the equivalences noted earlier for $a,b,c$, you have $ac = b^2=b=1$, in other words, which is not ensured in the left expression's expansion. This allows for further simplification of terms, knocking out some terms in the final expansion!
Since these terms can be eliminated, your suggested formula does not work. In general, if you can establish similar relationships among the various $x_i$'s - like a product of various $x_i$ is equal to a different $x_i$ - the formula suggested doesn't hold, because simplification goes on that eliminates some terms.