1
$\begingroup$

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$?

$\endgroup$
  • 1
    $\begingroup$ Did you learn generating functions? Seems like they would be apropos.. $\endgroup$ – windircurse Mar 11 '17 at 12:29
  • $\begingroup$ 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 $\endgroup$ – Elaqqad Mar 11 '17 at 12:32
  • $\begingroup$ @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. $\endgroup$ – Aayush Dwivedi Mar 11 '17 at 12:45
  • $\begingroup$ 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 $\endgroup$ – Elaqqad Mar 11 '17 at 13:02
2
$\begingroup$

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.

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

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.

$\endgroup$
  • $\begingroup$ 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) $\endgroup$ – Elaqqad Mar 11 '17 at 12:37
  • $\begingroup$ Is there any way to evaluate the former expression? $\endgroup$ – Aayush Dwivedi Mar 11 '17 at 12:38
  • $\begingroup$ Yes. An explanation for this "No" would be great. $\endgroup$ – Aayush Dwivedi Mar 11 '17 at 12:40
  • $\begingroup$ I am still stuck on this one from yesterday ... math.stackexchange.com/questions/2180428/integral-equation $\endgroup$ – Donald Splutterwit Mar 11 '17 at 12:45
  • $\begingroup$ 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 :-) $\endgroup$ – Donald Splutterwit Mar 11 '17 at 12:50

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.