No of integral solutions with finite repetition using generating function

Question

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 !

Answer 1

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*}

Comment:

• 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*}