1
$\begingroup$

I am wondering how many nonnegative solutions the following Diophantine equation has: $$x_1+x_2+x_3+\dots+x_n=r$$ if $x_1 \leq x_2 \leq x_3 \leq \dots \leq x_n$

I know if a sequence can be non-decreasing answer is $ {n+r-1}\choose{r} $

Can I use this fact to solve the problem? Thanks for help!

$\endgroup$
5
  • $\begingroup$ Yes, you could take $\binom{n+r-1}{r}$ and divide by the number of permutations, i.e. $n!$. But you have to work out the details. $\endgroup$
    – garondal
    Commented Dec 30, 2020 at 9:21
  • 2
    $\begingroup$ I don't think that's correct. It has problem when some elements are equal. also $ \binom{n+r-1}{r} $ is not always divisible on n!. $\endgroup$
    – mate zhorzholiani
    Commented Dec 30, 2020 at 9:33
  • 4
    $\begingroup$ You are correct. I don't think that you can solve it that simple. The solution is quite complicated: en.wikipedia.org/wiki/Partition_function_(number_theory) $\endgroup$
    – garondal
    Commented Dec 30, 2020 at 9:44
  • 1
    $\begingroup$ The OP problem reduces to partition function only when $n \ge r$, otherwise some solutions must be discarded, in any case I believe there is no known formula. $\endgroup$
    – Fabius Wiesner
    Commented Dec 30, 2020 at 10:13
  • $\begingroup$ Hy to clarify the question it seems $n$ is fixed, if so it could be calculated in a way... $\endgroup$
    – Toni Mhax
    Commented Jan 1, 2021 at 11:39

1 Answer 1

Reset to default
1
$\begingroup$

You're asking for the number of integer partitions with up to $n$ parts whose sum is $r$. (If $r < n$, then some of the $x_i$ must be 0.) The triangle of values is given in the On-Line Encyclopedia of Integer Sequences as A026820 (which uses $n$ for your $r$ and $k$ for your $n$). If you express this as a sum of partition counts with exactly $k$ parts A008284, you can generate an expression in terms of $p(n)$, the number of partitions of $n$, although this has no simple closed form.

The binomial coefficient $\binom{n+r-1}{r}$ would be relevant without the restriction that $x_1 \le x_2 \le \cdots \le x_n$. In that case you would be dealing with integer compositions, which are often easier to analyze than partitions.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .