5
$\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!

  • 1
    See: http://en.wikipedia.org/wiki/Partition_function_%28number_theory%29#Partition_function2011-10-28
  • 0
    $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.2011-10-28
  • 0
    So $r$ is fixed in your question? That's not clear, because the subject doesn't include $r$, I was assuming arbitrary length.2011-10-28
  • 0
    @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?2011-10-28
  • 0
    @AMPerrine: Right! I had corrected myself just before commented.2011-10-28
  • 0
    @Thomas: If I get what you're saying, r is chosen once, and then I'm interested in the number of integer solutions for that particular r: $x_1+...+x_r=k$ given the conditions. What should I say in my question to make this clearer?2011-10-28
  • 0
    Just say, "given fixed $k$ and $r$, how would I count..."2011-10-28
  • 0
    Okay, I'll edit my question to say that, thank you.2011-10-28
  • 0
    Technically, you don't need $x_r\leq k$ since the fact that the $x_i$ are positive and add up to $k$ means that $x_r\leq k$.2011-10-28
  • 0
    That article is only slightly relevant now that I've found out that you meant $r$ to be fixed, but it does still have one point, which is that this sort of partition counting is not easy - there tend to be no "nice" forms for this sort of counting problem.2011-10-28
  • 0
    Also, note that your expression not only "isn't very nice," it's actually wrong, since, $k=4,r=2$ has only 3 solutions, and your formula gives ${5\choose 1}+{4\choose 1}+{3\choose 1}=12$2011-10-28
  • 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

2

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