Find number of distinct terms in a multinomial expansion

binomial theoremmultinomial-coefficientsmultinomial-theorem

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??

Best Answer

Let us equivalently find the number of different monomials in

$$ f=(x^2)^{15}\left(\frac{1}{x^2}+\frac{1}{x}+x+x^2\right)^{15} = \left(1 + x + x^3 + x^4\right)^{15} $$

(after collecting them and writing the polynomial w.r.t. the basis $1,x,x^2,\dots$), which is a reciprocal polynomial of degree $4\cdot 15=60$. It is clear that there are at most $61$ terms (in the degrees $0,1,2,\dots,60$), so let us show that each degree is indeed taken. It is enough to check each degree up to $30$, the polynomial $f$ being reciprocal. We compute $$ (x^4 + x^3 + x + 1)^2 =x^{8} + 2 x^{7} + x^{6} + 2 x^{5} + 4 x^{4} + 2 x^{3} + x^{2} + 2 x + 1 $$ and see that each degree in the range $0,1,\dots,8$ is taken. So each degree in $\color{red}1\cdot(x^4 + x^3 + x + 1)^{2\cdot 7}$, and in particular also in $$ f= (x^4 + x^3 + x + \color{red}1)\cdot(x^4 + x^3 + x + 1)^{2\cdot 7}$$ between $0$ and $8\cdot 7$ is taken.

Related Solutions

[Math] The number of terms in the Multinomial Expansion $(x+\frac{1}{x}+x^2+\frac{1}{x^2})^n$

We obtain \begin{align*} \color{blue}{\left(x+\frac{1}{x}+x^2+\frac{1}{x^2}\right)}&=\frac{1}{x^{2n}}(1+x+x^2+x^3)^n\\ &=\frac{1}{x^{2n}}\left(1+x+x^3\left(1+x\right)\right)^n\\ &=\frac{1}{x^{2n}}(1+x)^n(1+x^3)^n\\ &\color{blue}{=\frac{1}{x^{2n}}\sum_{j=0}^n\binom{n}{j}x^j\underbrace{\sum_{k=0}^n\binom{n}{k}x^{3k}}_{n+1\text{ terms}}}\tag{1} \end{align*}

Let's have a look at the three factors in (1).

The rightmost sum contains $n+1$ pairwise different terms with exponents $3k,0\leq k\leq n$.
The leftmost factor $\frac{1}{x^{2n}}$ does not change the number of different terms as it is just a shift of each exponent of $x$ by $-2n$.
Now we assume $n\geq 2$ and analyse the left sum. A multiplication with the first three terms $\binom{n}{0},\binom{n}{1}x,\binom{n}{2}x^2$ results in $3(n+1)$ terms \begin{align*} \sum_{j=0}^n a_kx^{3k\color{blue}{+0}},\sum_{j=0}^n b_kx^{3k\color{blue}{+1}},\sum_{j=0}^n c_kx^{3k\color{blue}{+2}} \end{align*} which gives a sum of increasing powers of $x^k, 0\leq k\leq 3(n+1)$. Additionally we observe that whenever $n(>2)$ is increased by $1$, the overall number of terms is increased by $1$.

We conclude: The number of different terms in the expansion of $\left(x+\frac{1}{x}+x^2+\frac{1}{x^2}\right)^n$ is \begin{align*} \color{blue}{1}&\qquad \color{blue}{n=0}\\ \color{blue}{4}&\qquad \color{blue}{n=1}\\ 3(n+1)+(n-2)=\color{blue}{4n+1}&\qquad \color{blue}{n\geq 2} \end{align*}

Multinomial – Sum of coeffecients with even powers

This is not an answer to the combinatorial question, but it can help to check whether a combinatorial answer could be correct.

The following code constructs the polynomial via python's sympy and loops through the coefficients. Here p.coeff() is a list of all coefficients. p.monoms is a list of tuples with the degree of each variable. sum([m % 2 for m in monom]) == 0]) is a way to select all tuples that have only even terms.

from sympy import symbols, poly

k = 6
m = 6
n = 6
x = [symbols(f'x{i}') for i in range(1, n + 1)]
p = poly((k + sum(x)) ** m)
print(sum([coeff for coeff, monom in zip(p.coeffs(), p.monoms()) if sum([m % 2 for m in monom]) == 0]))

The result is 217392.

Best Answer

Related Solutions

[Math] The number of terms in the Multinomial Expansion $(x+\frac{1}{x}+x^2+\frac{1}{x^2})^n$

Multinomial – Sum of coeffecients with even powers

Related Question