I have the following problem:
Find the Coefficient of $x^{1397}$ in expansion of $(x^3+x^4+x^5+…)^6$
I know how to solve these kind of questions using Multinomial Theorem but since the polynomial in this one is infinite I’m lost!
Thanks in advance.
Multinomial Coefficient of $x^{1397}$ in expansion of $(x^3+x^4+x^5+…)^6$
combinatoricsmultinomial-coefficients
Related Solutions
Ok let's look at the card dealing example.
You are correct that the problem can be trivially solved by using multinomial coefficient. A good graphical representation of this can be found here: Multinomial Coefficient example
It is true that the correct answer is: $$\frac{52!}{13!13!13!13!}$$ So there are some issues with your permutation method......
The first problem with your permutation approach is that the permutations should be: $$P(52,13)*P(39,13)*P(26,13)*P(13,13)$$ instead of: $$P(52,13)*P(52,13)*P(52,13)*P(52,13)$$ because you can't deal the cards that have already been dealt to other people.
And the second problem is that the result from using multinomial coefficient does not care about the order at which the cards have been dealt (see link!). That means you will need combinations instead of permutations: $$C(52,13)*C(39,13)*C(26,13)*C(13,13)$$ expanding this gives you: $$\frac{52!}{39!13!}\frac{39!}{26!13!}\frac{26!}{13!13!}\frac{13!}{0!13!}$$ which is equivalent to the correct answer.
Hint: Write the polynomial as $$ x^n\cdot (1-x^{k})^n\cdot (1-x)^{-n}\tag 1 $$ then take the convolution of the generating functions for the last two factors: \begin{align} (1-x^k)^n&=\sum_{j=0}^n \binom{n}j(-1)^j x^{kj},\\ (1-x)^{-n}&=\sum_{j=0}^\infty \binom{-n}j(-1)^j x^j=\sum_{j=0}^\infty \binom{n+j-1}{n-1} x^j\tag 2 \end{align} You want the coefficient of $x^i$ in $(1)$, which is the same as the coefficient of $x^{i-n}$ in the product of the series in $(2)$.
Edit: To explain the part about $\binom{-n}j$. Note that when $n$ is positive, we have the usual formula $$ \binom{n}k=\frac{n(n-1)\dots (n-k+1)}{k!} $$ What is nice about the expression on the right is that it makes sense for negative (or even complex) $n$. When you substitute a negative value for $n$, you get \begin{align} \binom{-n}{k} &=\frac{(-n)(-n-1)\cdots (-n-k+1)}{k!} \\&=(-1)^k\frac{n(n+1)\cdots (n+k-1)}{k!} \\&=(-1)^k\binom{n+k-1}{k} \end{align} Furthermore, this natural generalization also agrees nicely with the binomial theorem. With this definition, it turns out that the Taylor series expansion $$ (1+x)^n=\sum_{k=0}^\infty \binom{n}k x^k $$ holds when $n$ is negative, or even complex. These two points justify $(2)$.
Best Answer
You are finding the coefficient of $x^{1397 - 3 \times 6} = x^{1379}$ of $(1 + x + x^2 + \cdots)^{6}$. Since you don't have to care about the term after $x^{1379}$ in $1+ x+ x^2+ \cdots$, you are finiding the coefficient of $x^{1379}$ of $(1+ x + x^2 + \cdots + x^{1379})^6$.
If you are not bounded to use the multinomial theorem, my suggestion is to find the taylor series of $(1+x+\cdots)^6 = \frac{1}{(1-x)^6}$ and find the $1379$th coefficient.