2
$\begingroup$

How to get coefficient with $t^{10}$ in $(1+t+t^2+t^3+t^4+t^5)^{10}$ ?

I tried to treat that as number of solutions of $$x_1+x_2+\cdots + x_{10} = 10 $$ where $x_i \in \left\{0,1,...,5 \right\} $ but writing solutions from scratch is very long work.

$\endgroup$
7
$\begingroup$

If you are wishing to do this by hand and not resort to using a computer, then your approach of treating it as the number of solutions of $x_1+x_2+\dots+x_{10}=10$ where $x_i\in\{0,1,\dots,5\}$ is a good one. We will of course not be writing out all solutions by hand however, that would be silly.

We continue with inclusion-exclusion.

The number of solutions to the system $x_1+x_2+\dots+x_{10}=10$ where $x_i\geq 0$ but with no upper limit can be found with stars-and-bars to be $\binom{10+10-1}{10-1}=\binom{19}{9}$

Now, supposing that one specific $x_i$ had violated the upper bound condition, then that $x_i$ would need to be at least six. WLOG suppose it was the first. We would have the system $x_1+x_2+\dots+x_{10}=10,~x_1\geq 6,~x_i\geq 0$ for all other $i$. Making a change of variable by setting $y_1=x_1-6$ we have instead the system $y_1+x_2+x_3+\dots+x_{10}=4,y_1\geq 0, x_i\geq 0$ which we can solve again with stars and bars as being $\binom{4+10-1}{10-1}=\binom{13}{9}$

Note that it is impossible for more than one upper bound condition to be violated and still have the sum be $10$ as that would require at least two terms whose values were at least six making the sum at least twelve.

Finally, noting that each $x_i$ could have been the one who violated the upperbound we get a final corrected total of:

$$\binom{19}{9}-10\cdot \binom{13}{9} = 85228$$

This can be verified by using a computer and just expanding the product as well:

wolfram results


As a final note, if we were looking for the coefficient of $t^{30}$ or something else larger where it would be possible for multiple values of $x_i$ to violate the upper bound condition, then we would continue with inclusion-exclusion. After having subtracted the number of ways to have one guaranteed (but still possibly more) value who exceeds the upper bound we would then go and add back the number of ways to have two guaranteed values who exceed the upper bound, subtracting again the number of ways to have three guaranteed values who exceed the upper bound and so on.

$\endgroup$
  • $\begingroup$ Your solution is very tricky. Correct me if I am wrong: You found a number of all solutions (if $ 10\ge x_i\ge0$) and you exclude solutions where $\exists_i x_i \ge 6$, is that right? $\endgroup$ – Tester1998 Aug 15 at 16:24
  • $\begingroup$ @Tester1998 I found all solutions where there wasn't an upper bound at all, so the "$10\geq$" in "$10\geq x_i\geq 0$" is unnecessary. Yes, I did then exclude those solutions where there was at least one $x_i$ satisfying $x_i\geq 6$., but to do this correctly one must be careful and account for the fact that we may have overcounted the number of such solutions if we have multiple who violate the condition rather than just one. It doesn't play much of a role in this problem since the value was so small that only one could violate the condition, but it becomes important in related problems. $\endgroup$ – JMoravitz Aug 15 at 16:31
2
$\begingroup$

Note that $$ (1+t+t^2+t^3+t^4+t^5)^{10}=\frac{(1-t^6)^{10}}{(1-t)^{10}}=(1-10t^6+\binom{10}{2}t^{12}+\dotsb+t^{60})\times (1-t)^{-10}\tag{0} $$ where we used the identity for a finite geometric series and the binomial theorem. Use the extended binomial theorem (or repeated differentiation of the identity $(1-t)^{-1}=\sum_{n=0}^\infty t^n$ or stars and bars) to write $$ (1-t)^{-10}=\sum_{n=0}^\infty \binom{n+10-1}{10-1}t^n=\sum_{n=0}^\infty \binom{n+9}{9}t^n\tag{1}. $$ From the product in $(0)$ our desired coefficient will be the coefficient of $t^{10}$ in $(1-t)^{-10}$ minus $10$ times the coefficient of $t^4$ in $(1-t)^{-10}$. So our final answer is $$ \binom{19}{9}-10\binom{13}{9}. $$

$\endgroup$
0
$\begingroup$

**Hint ** $$f(t)=(1+t+t^2+t^3+t^4+t^5)^{10}=\sum_{k} a_k t^k$$

Then $$ a_{10}= \frac{f^{(10)}(0)}{10!}$$

You can calculate the 10th derivative of $f$ via the method mentioned in this answer: nth derivative of a function to an arbitrary power

$\endgroup$
  • $\begingroup$ Doesn’t Faà di Bruno’s formula require iterating over all partitions of 10? Sounds potentially more tedious than counting restricted partitions of 10 (which OP wishes to avoid), no? $\endgroup$ – Erick Wong Aug 15 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.