Finding the Coefficient for a Generating Function

Question

I was doing a counting problem and came across the following generating function: $$\left(\sum_{i=0}^{7}x^i\right)^{100}=699.$$ I want to find the coefficient for $x^{699}.$ I tried to transform the equation into its equivalent form, the expression $$\left(\frac{x^8-1}{x-1}\right)^{100}.$$ However, I have no idea how to proceed. Can someone help me with this? Thanks a lot!

Answer 1

You'll need to use the extended binomial theorem. First rewrite your function as $(x^8-1)^{100}(x-1)^{-100}$. Your goal now will be to total the number of ways of selecting $x^8$ and $x^1$ such that the sum is $699$. For example, you could select $87$ of the $x^8$ terms and $3$ of the $x^1$ terms; the number of ways of doing this is $\binom{100}{87}\binom{-100}{3}=\binom{100}{87}\binom{102}{3}$. To this you would add the number of ways of selecting $86$ of the $x^8$ terms and $11$ of the $x^1$ terms, and so on. In total, you will need to compute $\sum_{i=0}^{12}\binom{100}{87-i}\binom{102+8i}{3+8i}$

The extended binomial theorem states that $\binom{-n}{k}=\binom{n+k-1}{k}$. Now you have all you need, but it will be a tedious calculation resulting in a very large number. I'd advise using a computer program.

Answer 2

Consider the polynomial of degree $~700~$ given by

$$(1 + x + x^2 + \cdots + x^7)^{100}. \tag1 $$

Visualize the multiplication as follows:

(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) times
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) times
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) times
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) times
....
(1 + x + x^2 + x^3 + x^4 + x^5 + x^6 + x^7) 

where you have $~100~$ different factors.

The only way of achieving the product of $~x^{700}~$ is if the $~x^7~$ term was selected from each of the $~100~$ factors. Therefore, the coefficient of the $~x^{700}~$ term must be $~1.~$

Similarly, the only way of achieving the product of $~x^{699}~$ is if the $~x^7~$ term was selected from $~99~$ of the factors, and the $~x^6~$ term was selected from exactly one of the factors. Therefore, the coefficient of the $~x^{699}~$ term must be $~100.~$

---

$\underline{\text{Addendum}}$

The portion of my answer before the addendum ducked the much more difficult question. For any $~n \in \{2,3,\cdots, 698\},~$ how do you analytically compute the coefficient of the $~x^n~$ term in the $~(1 + x + x^2 + \cdots + x^7)^{100}~$ product?

For this much more difficult question, I can not improve on the elegant approach given in the answer of H. sapiens rex.

Answer 3

The polynomial can be expanded term by term which leads to \begin{align} \left( \sum_{k=0}^{7} x^k \right)^{100} = 1 + 100 \, x + 5050 \, x^2 + 171700 \, x^3 + \cdots + 171700 \, x^{697} + 5050 \, x^{698} + 100 \, x^{699} + x^{700}. \end{align} This is essentially the long result of using multinomial coefficients, which either coefficients of $x$, or $x^{699}$, can be obtained from the coefficient $$ \binom{100}{1, 1, 1, 1, 1, 1, 1} = \frac{(100)!}{1! \, 1! \, 1! \, 1! \, 1! \, 1!, (99)! } = 100. $$ This is the same result found by the expansion of the polynomial.

Answer 4

$$f(x)=(1+x+x^2+\dots+x^7)^{100}$$ is the generating function for the number of integer solutions to $$z_1 + z_2 + \dots + z_{100}=r $$ subject to $0 \le z_i \le 7$ for $1 \le i \le 100$. The coefficient of $x^{699}$ is the number of solutions in the case $r=699$. But in order to have $$z_1 + z_2 + \dots + z_{100}=699 $$ subject to the stated constraints, it must be that $z_i = 7$ for all $1 \le i \le 100$ with exactly one exception, say $z_j$, with $z_j = 6$. There are $100$ ways to choose $j$, so the number of solutions is $100$, i.e. $$[x^{699}]f(x) = 100$$