# Number of integer solutions if $x_1\leq x_2\leq x_3\leq \cdots\leq x_r\leq k$

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...

• – Thomas Andrews Oct 28 '11 at 14:53
• $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. – AMPerrine Oct 28 '11 at 14:58
• So $r$ is fixed in your question? That's not clear, because the subject doesn't include $r$, I was assuming arbitrary length. – Thomas Andrews Oct 28 '11 at 15:03
• @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? – roel Oct 28 '11 at 15:04
• @AMPerrine: Right! I had corrected myself just before commented. – 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".

• 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. – 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)$.

• 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! – 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

• 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 – Thomas Andrews Oct 28 '11 at 15:16