How would I count the number of integer solutions to: $x_1+x_2+\cdots+x_r=k$, given fixed $r$ and $k$ and $0\leq x_1\leq x_2\leq \cdots \leq x_r\leq k$?

Attempt at solution (incorrect, see per comments): I was thinking maybe I could exchange this for the number of integer solutions to: $y_1+y_2+\cdots+y_r=x_r$ where $y_1=x_1, y_{i>1}=x_i-x_{i-1}$, but then it gets a little messy because there are multiple possible values for $x_r$ for a given $k$... I think $x_r$ can be at minimum $k/r$ rounded down (edit: nope... rounded up?), in which case the answer would be $\sum_{[k/r]\leq j\leq k}\binom{j+r-1}{r-1}$ but this isn't the nicest expression...

Thanks for your help!

  • 1
    $\begingroup$ See: en.wikipedia.org/wiki/… $\endgroup$ – Thomas Andrews Oct 28 '11 at 14:53
  • $\begingroup$ $k=x_1+x_2+\cdots+x_r\leq rx_r\Rightarrow x_r\geq \frac{k}{r}$. So you should round up, not down. $\endgroup$ – AMPerrine Oct 28 '11 at 14:58
  • $\begingroup$ So $r$ is fixed in your question? That's not clear, because the subject doesn't include $r$, I was assuming arbitrary length. $\endgroup$ – Thomas Andrews Oct 28 '11 at 15:03
  • $\begingroup$ @Thomas: thank you, but I'm afraid I didn't quite get to the bottom of that article... maybe you could post an answer explaining things a bit more simply? $\endgroup$ – roel Oct 28 '11 at 15:04
  • $\begingroup$ @AMPerrine: Right! I had corrected myself just before commented. $\endgroup$ – roel Oct 28 '11 at 15:04

You can count these partitions by recursion.

Let $p_n(x,y)$ be the number of partitions of $x$ into up to $y$ parts where the largest part is less than or equal to $n$. You can start with $p_0(x,y)=0$ when $x>0$, $p_n(x,y)=0$ when $x \lt 0$; and $p_n(0,0)=1$; and . The key element is $$p_n(x,y)=p_{n-1}(x,y)+p_{n}(x-n,y-1)$$ and you want $p_k(k,r)$.

I have a Java applet here which does the calculation: type $k$ next to "Partitions of:", change "Any number of terms" to "Maximum number of terms:" and type $r$, and finally click on "Calculate partitions".

  • $\begingroup$ This is more complex than I thought it would be, but apparently it can't get any simpler than that. I can understand the answer and the program is helpful, so I accepted your solution. $\endgroup$ – roel Oct 28 '11 at 16:31

Let $p(k,r)$ be the number you are looking for.

Your formula can't be right, because $p(k,r)$ is constant when $r\geq k$. That is:

$$\forall r\geq k: p(k,r) = p(k,k)$$

That's the case because at most $k$ of the $x_i$ can be positive, so the only solutions when $r\geq k$ can be solutions when $r=k$ plus an additional $r-k$ zeros.

On the other hand, your formula increases for all $r$.

The generating function for $p(k,r)$ is:

$$\sum_{k,r} {p(k,r)x^ky^r} = \prod_{j=0}^\infty{\frac{1}{1-x^jy}}$$

It is unlikely you'll find a nice formula for $p(k,r)$, given their relation to the rather complex partition function $P(n)$.

In particular, $p(k,k)=P(k)$.

  • $\begingroup$ Thank you for helping me understand the question. Ultimately Henry's question was a bit more understandable to me so I accepted it, but I thank you for your efforts and time! $\endgroup$ – roel Oct 28 '11 at 16:56

introduce k-1 dummy variables that would help u remove all the <= and covert them to < between all the 0<=x1----- then u can simply use the formula n+r-1Cr

  • 1
    $\begingroup$ No, that doesn't work. If $k=4$ and $r=2$, you can write it in exactly three ways, $4 = 0+4 = 1+3 = 2+2$. But ${{k+r-1}\choose r} = 10$. The number of ways of partitioning $k$ into $r$ numbers in any order is ${k+r-1}\choose{r-1}$, which is probably the formula you are thinking of $\endgroup$ – Thomas Andrews Oct 28 '11 at 15:16

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.