6
$\begingroup$

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!

  • 0
    Yeah, I figured that some minutes ago. It seems to not work for most ks and rs, probably because I ignored the dependency between the $y_i$s?2011-10-28

3 Answers 3

3

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

  • 0
    This is more complex th$a$n I thought it would be, but apparently it can't get any si$m$pler than that. I can understand the answer and the progra$m$ is helpful, so I accepted your solutio$n$.2011-10-28
2

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

  • 0
    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!2011-10-28
0

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
    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 of2011-10-28