Find a coefficient of $x^{12}$ in $(x + x^{2} +x^{3} +x^{4})^{5}$

Question

Find a coefficient of $x^{12}$ in $$(x + x^{2} +x^{3} +x^{4})^{5}$$

Using formula for the sum of a geometric series I have turned it into $$x^5(1-x^4)(1-x)^{-4} $$

So now I see that in $(1-x^4)(1-x)^{-4}$ we need to find coefficient of $x^7$ as we actually have $x^5$, am I right?

If so I unfortunately still don't know what I should do as my next step to calculate this coefficient.

Answer 1

That is the same as the number of integral solutions to $x_1+x_2+x_3+x_4+x_5=12$ where $1\le x_i\le 4$ for all i.

There is a one-to-one bijection between solutions to this diophantine equation and $y_1+y_2+y_3+y_4+y_5 = 7$ where $0\le y_i \le 3$. There are $\dbinom{11}{4}$ integral solutions with no upper bounds. There are $\dbinom{7}{4}$ solutions that violate each bound. So, the coefficient of $x^{12}$ from your problem is $\dbinom{11}{4}-5\dbinom{7}{4} = 155$

Answer 2

It is the coefficient of $x^7$ in:

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

The first two terms of the numerator are $(1-x^4)^5=1-5x^{4}+\dots$ with the other terms of degree $8$ or more, so we can ignore them. Now, if $\frac{1}{(1-x)^5}=\sum_{n=0}^{\infty} a_nx^n$ then the coefficient we are looking for is the coefficient of $x^7$ in:

$$(1-5x^4)\sum a_nx^n$$

Which is $a_7-5a_3.$

Ao do you know the sequence $\{a_n\}$?

---

This can also be written as an inclusion-exclusion result. Let $A$ be the set of all integer solutions to $x_1+x_2+x_3+x_4+x_5=7$. Let $A_i$ be the subset of all such solutions with $x_i\geq 4.$

Note that $A_i\cap A_j=\emptyset$ if $i\neq j$, and all the $A_i$ are the same size, so you get:

$$|A|-5|A_1|.$$

That looks similar. :)

Answer 3

Determine the cardinality of $I=\{ i \in \{1,2,3,4\}^5 | i_1 +i_2 +i_3 +i_4 +i_5= 12\}$.

Stars & bars (https://en.wikipedia.org/wiki/Stars_and_bars_(combinatorics)#Theorem_one_2) gives 5 bins with 12 objects, hence $\binom{12-1}{5-1}$.

The problem with the stars & bars approach is that $i \in \mathbb{N}^5$ rather than $i \in \{1,2,3,4\}^5$. We need to remove the 'large' $i$s.

This is straightforward to address once we notice that in any 'large' $i$, at most one $i_k \in \{5,...,8\}$.

If we pick $m \in \{5,...,8\}$, then number of 'large' $i$s with some $i_k = m$ is $5 |\{ j \in \mathbb{N}^4 | i_1 +i_2 +i_3 +i_4 = 12-m \}|$, hence using stars & bars again, we see that the number of large $i$s is $5 \sum_{m=5}^8 \binom{11-m}{3}$, which we can compute using the hockey stick identity (https://en.wikipedia.org/wiki/Hockey-stick_identity) as $5 \binom{7}{4}$.

Hence we obtain the result $\binom{11}{4}-5\binom{7}{4}$.

Answer 4

you can have a look at this post too : Coefficient of $x^{25}$

$$(x+x^2+x^3+x^4)^5=\sum\limits_{i+j+k+l=5} \binom{5}{i,j,k,l}x^{i+2j+3k+4l}$$

The coefficient $x^{12}$ is obtained when $i+2j+3k+4l=12$.

$\begin{array}{cccc|c} i & j & k & l & \dfrac {5!}{i!j!k!l!}\\\hline 0 & 3 & 2 & 0 & 10\\ 0 & 4 & 0 & 1 & 5\\ 1 & 1 & 3 & 0 & 20\\\ 1 & 2 & 1 & 1 & 60\\ 2 & 0 & 2 & 1 & 30\\ 2 & 1 & 0 & 2 & 30\\\hline &&&&155\end{array}$