Give a formula for the number of integer solution of the system with the solutions $\geq 0 $ $$x_1+x_2+\dots +x_r=n$$ $$y_1+y_2+\dots + y_r=n$$ With the condition that: $x_1+y_1\geq 1,\dots ,x_r+y_r\geq 1$

So I tried adding both equations so I got: $$x_1+y_1+\dots +x_r+y_r=2n$$

And made a change of variable called $z_i=x_i+y_i-1$ and the number of solutions of the new system will be the same that the original one so we have: $$z_1+\dots +z_r = 2n-r$$ and the number of solutions of this equation is: $\binom{2n-1}{r-1}$.

Is this correct?

  • $\begingroup$ I don't think this is right. If you have a solution with say $z_1=7$ you have $8$ possible value of $(x_1,y_1)$ associated with it, and of course, the same goes for the other variables. $\endgroup$ – saulspatz Mar 5 at 12:34

Since the two equations have no variables in common, the number of solutions of the system is just the product of the numbers of solutions to each equation. If it were not for the side condition, we would have $${n+r-1\choose n}^2$$ solutions. We need to eliminate the solutions where $x_1= y_1=0$ but these are the solutions to a similar system with $r-1$ variables in each equation, so there are $${n+r-2\choose n}^2$$ of these. Of course, there are $r$ pairs of variables to deal with so we have $${n+r-1\choose n}^2-r{n+r-2\choose n}^2$$ solutions.

I'm sure you see what's coming. Solutions where two of the pairs are both $0$ have been subtracted twice, so we need to add them back in. Then we have to deal with three vanishing pairs, and so on. By inclusion-exclusion, we get $$\sum_{k=0}^{r-1}(-1)^k{r\choose k}{n+r-1-k\choose n}^2$$

I don't know if this can be simplified further.


I checked this manually for $n=4,r=3$ and it gives the correct solution of $153.$

  • $\begingroup$ Really thank you. I'm starting at combinatorics and I'm being terrible at it. This truly will help me. $\endgroup$ – iggykimi Mar 5 at 13:23

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.