# Number of solutions of $x_1 + 2x_2 + 3x_3 + \cdots + n x_n = p$

Given a non-negative integer $$p$$. What is the number of solutions of $$x_1+2x_2+3x_3 + \cdots + nx_n = p$$, where the $$x_i$$'s are non-negative integers.

Can we answer this by using number of solutions of $$x_1+x_2+x_3 + \cdots + x_m = q$$ for any $$m,q$$?

• Did you learn generating functions? Seems like they would be apropos.. – windircurse Mar 11 '17 at 12:29
• The number of solutions to the first equation, is equal to the number of solutions to the second equation for $m=n$ and $p=q$ and all $x_i$s are different, and it's called the number $p_m(q)$ of partitions of $q$ into exactly $m$ parts ". There is a lot of mathematical research in how to compute these numbers, but they don't have a closed form, except complicated formalus and relating to coefficients of generating functions which are also hard to compute – Elaqqad Mar 11 '17 at 12:32
• @Elaqqad How are the number of solutions same. I am very sure they are not. I think you misunderstood the question. I can provide a counterexample if you need. – Aayush Dwivedi Mar 11 '17 at 12:45
• that's not what I wrote !, they are the same if we require in the second equution the $x_i$ s to be all distincts – Elaqqad Mar 11 '17 at 13:02

The number of nonnegative integer solutions of $x_1 + 2 x_2 + \cdots + n x_n = p$, where $p \geq 0$, is the coefficient of $t^p$ in the following generating function [JDL]

$$\prod_{k=1}^n \frac{1}{1-t^k} = \frac{1}{(1-t) (1-t^2) \cdots (1-t^n)}$$

[JDL] Jesús A. De Loera, The Many Aspects of Counting Lattice Points in Polytopes.

• Is there any closed form solution? Or any $\mathcal{O}(n)$ solution or something like that. – Aayush Dwivedi Mar 11 '17 at 12:49
• I don't know. Take a look at the Cauchy product. – Rodrigo de Azevedo Mar 11 '17 at 15:02

The number of solutions of $x_1+2x_2+ \cdots +nx_n=p$ is given by the coefficient of $x^{p}$ in \begin{eqnarray*} \frac{1}{(1-x)(1-x^2) \cdots (1-x^n) } \end{eqnarray*}

The number of solutions of $x_1+x_2+ \cdots +x_m=q$ is given by the coefficient of $x^{q}$ in \begin{eqnarray*} \frac{1}{(1-x)^m } \end{eqnarray*} So the answer to your question is no.

• maybe you should answer why the answer is no , because the question is : are the coefficients of the two generating functions related in some way ? ( using the generating function is just another terminology, just rephrasing the question in another way) – Elaqqad Mar 11 '17 at 12:37
• Is there any way to evaluate the former expression? – Aayush Dwivedi Mar 11 '17 at 12:38
• Yes. An explanation for this "No" would be great. – Aayush Dwivedi Mar 11 '17 at 12:40
• I am still stuck on this one from yesterday ... math.stackexchange.com/questions/2180428/integral-equation – Donald Splutterwit Mar 11 '17 at 12:45
• The latter expression is easily is easily evaluated $\binom{q}{m-1}$ . I am not aware of an easy way to evaluate the former expression ... so I guess there is no easy way to relate the two. ... this still avoids the crunch question ... sorry :-) – Donald Splutterwit Mar 11 '17 at 12:50