How many integral solutions of the following equation where $x_i$ and $k$ are integers.

$\begin{align*} &\sum_{i=1}^{10}x_i = k \quad \text{ where }\qquad 0\leq x_i \leq 20 \quad,\quad k > 0\\ &\text{Using generating function :} \\ &\text{No of solution : } \sum_{k=1}^{200}\left [ {\color{red}{\left [ x^k \right ]}}\left ( \sum_{p=0}^{20}x^p \right )^{10} \right ] \\ &\Rightarrow \sum_{k=1}^{200}\left [ {\color{red}{\left [ x^k \right ]}}\left ( \frac{1-x^{21}}{1-x} \right )^{10} \right ] \\ &\Rightarrow \sum_{k=1}^{200}\left [ {\color{red}{\left [ x^k \right ]}}\left \{ \sum_{m=0}^{10}\binom{10}{m}(-1)^mx^{21m} \right \}\cdot \left \{ \sum_{n=0}^{\infty}\binom{9+n}{n}x^n \right \} \right ] \\ \end{align*}$

Please help me to simplify the steps, it is getting cumbersome even to find coefficient of ${\color{red}{\left [ x^k \right ]}}$.

Or please suggest other method.

Thanks !


Here we extract the coefficient of $x^k$.

We obtain \begin{align*} [x^k]\sum_{n=0}^\infty&\binom{n+9}{n}x^n\sum_{m=0}^{10}\binom{10}{m}(-1)^mx^{21m}\\ &=\sum_{n=0}^k\binom{n+9}{n}[x^{k-n}]\sum_{m=0}^{10}\binom{10}{m}(-1)^mx^{21m}\tag{1}\\ &=\sum_{n=0}^k\binom{k-n+9}{k-n}[x^{n}]\sum_{m=0}^{10}\binom{10}{m}(-1)^mx^{21m}\tag{2}\\ &=\sum_{n=0}^{\left\lfloor{k/21}\right\rfloor}\binom{k-21n+9}{k-21n}[x^{21n}]\sum_{m=0}^{10}\binom{10}{m}(-1)^mx^{21m}\tag{3}\\ &=\sum_{n=0}^{\min\{\left\lfloor{k/21}\right\rfloor,10\}}\binom{k-21n+9}{k-21n}\binom{10}{n}(-1)^n\tag{4}\\ \end{align*}


  • In (1) we use the linearity of the coefficient of operator and apply the rule \begin{align*} [x^{p-q}]A(x)=[x^p]x^qA(x) \end{align*}

  • In (2) we exchange the order of summation of the outer sum by replacing $n \rightarrow k-n$.

  • In (3) we note that in the inner sum the exponent of $x$ is a multiple of $21$. So, we need multiples of $21$ of the index $n$ in order to match these exponents. We account for this by taking multiples of $21$ of the index $n$. This way we can also restrict the upper limit of the out sum.

  • In (4) we select the coefficient of $x^{21m}$ and update the upper limit of the sum accordingly.

Note: Since $\binom{p}{q}=0$ if $q>p$ we could also relax the upper bound of the sum and simply write \begin{align*} \sum_{n\geq 0}\binom{k-21n+9}{k-21n}\binom{10}{n}(-1)^n \end{align*}


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.