Find no. of terms in the expansion of $(1+x+x^2+x^3)^{11}$

Question

There is a formula to find the number of terms which is: ${n+r-1 \choose r-1}$, where $r$ is the no. if terms in the expression, but there are cases where this formula fails i.e. when the expression gets reduced to something else. I am confused about this particular problem as to how to calculate the no. of terms because going by the above mentioned formula I get $_{14}C_3 = 364$ but if I solve the expression I get $(1+x)^{11}(1+x^2)^{11}$ where the no. of terms will be less than $12\times12=144$. Any kind of explanation will help me clarify this topic.

Answer 1

The combinatorics here is easier than you seem to think. The highest degree term is $x^{33}$, and the lowest degree term is $1$. Also, each degree between is present. So there are $34$ terms.

Answer 2

Notice that the highest power of $x$ that could possibly appear in the expansion, followed by collection of like powers, is $x^{33}$. (You can see this by replacing "$11$" with "$1$", then "$2$", then "$3$", and so on until you see the pattern.) So the largest number of terms is $34$.

When you compute $(1+x+x^2+x^3)^2$, are all seven terms present? The $1$ from the first term ensures each of $1$, $x$, $x^2$, and $x^3$ terms appear in the expansion. Since all coefficients are positive, none of these can be cancelled by collecting like terms. Similarly, the $x$ from the first term ensures $x^4$ appears in the expansion (when multiplied by $x^3$ in the second term), the $x^2$ from the first term and the $x^3$ from the second term produce $x^5$ and both $x^3$s give an $x^6$. So all seven terms appear in the expansion and all survive in the collection.

When you compute $(1+x+x^2+x^3)^4$, are all thirteen terms present? This is also the square of $(1+x+x^2+x^3)^2$ which we know has terms of all degrees, starting at $1$ and ending at $x^6$. By an argument similar to the previous, we get terms $1$ through $x^6$ immediately from $1$ in the first term. then $x^6$ through $x^{12}$ immediately from $x^6$ in the first term. Again, collection cannot cancel terms, so we have terms from each degree from $1$ to $x^{12}$.

When you compute $(1+x+x^2+x^3)^8$, are all $25$ terms present? Repeating the "from the first term in the first factor" and "from the last term in the first factor", when writing this as a square of the previous calculation, we get all the degrees from $1$ through $x^{24}$.

Notice that we get each of these by squaring the previous one. So our exponent doubles in each step, just like the place values in binary. What is the binary representation of $11$?

Then, since $11 = 8+2+1$, when you compute $(1+x+x^2+x^3)^{11}$, are all $34$ terms present?

Answer 3

The number $$ \binom{n + r - 1}{r-1} $$ or better $$ \binom{n + r - 1}{n} $$ gives the
number of weak compositions of $n$ into $r$ parts ranging from $0$ to $n$.

As such, its ogf is $$ \eqalign{ & \left( {{1 \over {1 - x}}} \right)^{\,r} = \left( {1 + x + x^{\,2} + \cdots } \right)^{\,r} = \cr & = \underbrace {1 \cdot 1 \cdot \ldots \cdot 1}_{r\,terms} + 1 \cdot 1 \cdot \ldots \cdot x + 1 \ldots \cdot x \cdot 1 + \cdots = \cr & = \left( {1 - x} \right)^{\, - r} = \sum\limits_{0\, \le \,n} {\left( { - 1} \right)^{\,n} \left( \matrix{ - r \cr n \cr} \right)x^{\,n} } = \sum\limits_{0\, \le \,n} {\left( \matrix{ n + r - 1 \cr n \cr} \right)x^{\,n} } \cr} $$

You have instead $$ \left( {1 + x + x^{\,2} + \cdots + x^{\,q} } \right)^{\,r} = \left( {{{1 - x^{\,q + 1} } \over {1 - x}}} \right)^{\,r} = \sum\limits_{0\, \le \,n} {N_b (n,q,r)\,x^{\,n} } $$ and the coefficient $N_b(n,q,r)$ corresponds to the
number of weak compositions of $n$ into $r$ parts ranging from $0$ to $q$
so that when $q<n$ they differ from the above.

The formula for such coefficients is given by $$ N_b (s,r,m)\quad \left| {\;0 \leqslant \text{integers }s,m,r} \right.\quad = \sum\limits_{\left( {0\, \leqslant } \right)\,\,k\,\,\left( { \leqslant \,\frac{s}{r+1}\, \leqslant \,m} \right)} {\left( { - 1} \right)^k \binom{m}{k} \binom { s + m - 1 - k\left( {r + 1} \right) } { s - k\left( {r + 1} \right)}\ } $$ as explained in this post

Answer 4

As you note it, using binomial expansion, your expression can be written

$$(1+x)^{11}(1+x^2)^{11}=\sum_{p=0}^{11}\binom{11}{p}x^p\sum_{q=0}^{11}\binom{11}{q}x^{2q}=\sum_{p,q=0}^{11}\binom{11}{p}\binom{11}{q}x^{p+2q}$$

We claim that this expansion contains all monomials $ax^{k}$ between $k=0$ and $k=33$.

Indeed, any number $0 \le k \le 33$ can be represented (possibly in many ways) under the form :

$$k=p+2q \ \text{for certain} \ p,q \in [0,11]\tag{1}$$

Proof :

Let us establish that there is at least one way to do so.

Let $2q$ be the closest even number less or equal to $\min(k,22)$ ; in particular, we have $q \leq 11$ ; $k$ being at most $33$, the difference $p:=k-2q$ is at most equal to $11$, proving the existence of $p,q$ as desired by (1).

Remark : what we have done with $11$ could be done with any integer exponent.