2
$\begingroup$

The question is how many possible solutions there are for a equation system subject to the condition that $1 \leq x_1 + y_1$, $1 \leq x_2 + y_2$, $1 \leq x_r + y_r$ where $x_i$ and $y_i$ are non-negative integers.

The system is $$x_1 + x_2 + \ldots + x_r = n.$$ $$y_1 + y_2 + \ldots + y_r = n.$$

I want to do it by the inclusion-exclusion principle but i can't find a way to pose a initial equation. After that i would suppose $ 1 - y_1 > x_1 $ and try to introduce it in one of those equations.

Any help is greatly appreciated, thanks.

$\endgroup$
7
  • $\begingroup$ If $x_i,y_i$ are positive integers the conditions $x_i+y_i\ge1$ are always fulfilled. Therefore you can simply multiply the numbers of solutions for each equation. $\endgroup$
    – user
    Commented Mar 9, 2021 at 12:16
  • $\begingroup$ Feeding on the previous comment, see this Stars and Bars article. Note that (for example) the number of positive integer solutions to $$x_1 + x_2 + \cdots + x_r = n$$ is the same as the number of non-negative integer solutions to $$w_1 + w_2 + \cdots + w_r = (n-r).$$ $\endgroup$
    – user2661923
    Commented Mar 9, 2021 at 12:30
  • $\begingroup$ Ok thanks; and what would I have to do if integers can be non-positive?? $\endgroup$
    – Mr showman__
    Commented Mar 9, 2021 at 14:19
  • $\begingroup$ @Mrshowman__ If you want to change the question, you should edit the question itself. $\endgroup$
    – Mike Earnest
    Commented Mar 9, 2021 at 14:38
  • 2
    $\begingroup$ If you found my answer helpful, please accept $\checkmark$ and upvote if you want to. Otherwise feel free to ask for clarification in comments below the answer. $\endgroup$
    – Joffan
    Commented Mar 9, 2021 at 21:03

1 Answer 1

Reset to default
3
$\begingroup$

There may be a simpler solution, but you can certainly run this by inclusion-exclusion on a reducing $r$.

I'm thinking of this as being like deployment of $n$ infantry and $n$ artillery into a position with $r$ locations, where you cannot leave any gap in the line. Without the gap restriction we can easily see this is two cases of stars-and-bars for $\binom{n+r-1}{n}^2$

A gap in both categories ($x_i+y_i=0$) would correspond to a deployment into $r{-}1$ positions. The gap can occur in $\binom r1=r$ locations of course. Then we have to account for overcounting the case of $2$ gaps, etc., giving

$$\sum_{k =0}^{r-1}(-1)^k\binom{r}{k}\binom{n+r-1-k}{n}^2 $$

$\endgroup$
2
  • $\begingroup$ Hi, the explanation is really good, but i can't understand the final formula. I mean i don't understand why the gap can occur in those locations and why the overcountinig give this formula. $\endgroup$
    – Mr showman__
    Commented Mar 15, 2021 at 23:18
  • $\begingroup$ The inclusion-exclusion proceeds with alternating signs for over counting and undercounting, for a reducing number of positions selected in different ways from the original set. $\endgroup$
    – Joffan
    Commented Mar 16, 2021 at 1:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .