5
$\begingroup$

My discrete math textbook has the following solution to the problem using generating functions (the solution has to use generating functions):

$$f(x)=(x+x^2+x^3+x^4+x^5+x^6)^{10}$$

Once we start developing the formal power series we get the following:

$$x^{10}(1-x^6)^{10}\frac{1}{(1-x)^{10}}$$ Because of $x^{10}$ we now need to find the coefficient of only $x^{15}$: $$\binom{10}{0}\binom{10-1+15}{15}-\binom{10}{1}\binom{10-1+9}{9}+\binom{10}{2}\binom{10-1+3}{3}$$ I completely understand the first two expressions but why are we using the third one: $$\binom{10}{2}\binom{10-1+3}{3}$$ Where does the $3$ come from and why this isn't enough: $$\binom{10}{0}\binom{10-1+15}{15}-\binom{10}{1}\binom{10-1+9}{9}$$ ?

$\endgroup$
  • 1
    $\begingroup$ Can you explain your understanding of the first two terms? $\endgroup$ – Henning Makholm Aug 4 '16 at 19:35
  • $\begingroup$ As an aside, you have a typo in the first line. You write $(\color{red}{x}+x^1+x^2+\dots+x^6)$ where it should instead have been $(x^1+x^2+\dots+x^6)$. $\endgroup$ – JMoravitz Aug 4 '16 at 19:35
  • $\begingroup$ you're right corrected $\endgroup$ – Yos Aug 4 '16 at 19:44
5
$\begingroup$

The coefficient of $x^{25}$ in $(x+x^2+\ldots+x^6)^{10}$ equals the coefficient of $x^{15}$ in $$ (1+x+\ldots+x^5)^{10} = (1-x^6)^{10}\cdot\frac{1}{(1-x)^{10}} $$ so the answer is given by $$ [x^{15}] \left(\sum_{k=0}^{10}\binom{10}{k}(-1)^k x^{6k}\right)\cdot\left(\sum_{j\geq 0}\binom{9+j}{j}x^j\right) $$ and it is enough to consider just the terms associated with $k=0,1,2$, since $x^{6k}$ has an exponent greater than $15$ for any $k>2$. By computing the Cauchy product between the above series it follows that the answer is given by: $$ \underbrace{\binom{10}{0}\binom{24}{15}}_{k=0,\;j=15}-\underbrace{\binom{10}{1}\binom{18}{9}}_{k=1,\;j=9}+\underbrace{\binom{10}{2}\binom{12}{3}}_{k=2,\;j=3}.$$

$\endgroup$
  • 1
    $\begingroup$ thanks, I understood that I need to go back to sigma notation for better understanding how to solve such problems, thanks! $\endgroup$ – Yos Aug 4 '16 at 20:03
1
$\begingroup$

As opposed to generating functions, I personally learned to solve this question via inclusion exclusion.

We were looking for the number of integer solutions to the system: $\begin{cases} x_1+x_2+\dots+x_{10}=25\\ 1\leq x_i\leq 6&\text{for all}~i\end{cases}$

Through a change of variable, we have instead the system $\begin{cases}y_1+y_2+\dots+y_{10}=15\\ 0\leq y_i\leq 5\end{cases}$

Approaching via inclusion-exclusion on the events that the respective upper bound conditions are violated. Let $S$ be where we ignore any upper bound conditions. Let $A_i$ be the set where the $i$'th upper bound condition is violated. The total with no upperbound conditions violated is:

$$|S|-\sum\limits_{i=1}^{10}|A_i|+\sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}|A_i\cap A_j| - \sum\limits_{i=1}^{10}\sum\limits_{j=i+1}^{10}\sum\limits_{k=j+1}^{10}|A_i\cap A_j\cap A_k|+\dots$$

if we have no upper bound conditions violated, there are $\binom{10+15-1}{15}$ solutions. If one upper bound condition is violated, pick which one. Each of which will have a total of $\binom{10+9-1}{9}$ solutions for a total of $\binom{10}{1}\binom{18}{9}$ needing to be removed from the count. If two upperbound conditions are violated, pick which two they are. Each of which will have a total of $\binom{10+3-1}{3}$ solutions for a total of $\binom{10}{2}\binom{12}{3}$ needing to be added back. Three upperbound conditions being simultaneously violated is impossible.

This gives, again the solution of:

$$\binom{10}{0}\binom{24}{15}-\binom{10}{1}\binom{18}{9}+\binom{10}{2}\binom{12}{3}$$

The explanation for the final term being with this understanding, that you had subtracted the same "bad outcomes" from your total too many times otherwise. Why we use a $3$ would be from how we solve the question of finding how many violate the $i$'th and $j$'th upperbound conditions. Suppose $i=1$ and $j=2$, we have then the system:

$\begin{cases} y_1+y_2+\dots+y_{10}=15\\ 6\leq y_1\\ 6\leq y_2\\ 0\leq y_3\\ \vdots \\ 0\leq y_{10}\end{cases}$

After a change of variable, we have the system

$\begin{cases} z_1+z_2+\dots+z_{10}=3\\ 0\leq z_i\end{cases}$ which is of a known form.

$\endgroup$
  • $\begingroup$ thanks, I agree that the problem can be solved via inclusion/exclusion principle but the problem I posted had to be solved via generating functions. $\endgroup$ – Yos Aug 4 '16 at 20:04
  • 1
    $\begingroup$ My goal was to provide an alternate explanation to why the final term appeared the way it did is it may be more intuitive when viewed from a different angle. $\endgroup$ – JMoravitz Aug 4 '16 at 20:36

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.