2
$\begingroup$

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?

$\endgroup$
1
  • $\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$ Commented Mar 5, 2019 at 12:34

1 Answer 1

Reset to default
2
$\begingroup$

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.

EDIT

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

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

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.