1
$\begingroup$

To restate the constraints, I have $x,y$ as strictly positive integers not exceeding $n$. As a result, the number of solutions will be nonzero on the range $z \in [2, 2n]$.

My first reaction was to do it using inclusion/exclusion. First define $x' = x-1$, $y'=y-1$, $z'=z-2$ to take care of the lower bounds.

We now have $x',y' \in [0, n-1]$. If we let $P_x := x'\le n-1$ and $P_y := y'\le n-1$ and $N(C) := \text{the number of solutions satisfying C}$, then we arrive at the following inclusion exclusion sum.

$$N(P_xP_y) = N - N(P_x') - N(P_y') + N(P_x'P_y')$$

For the unconstrained case:

$$N = \binom{2+z'-1}{z'} = z' + 1 = z - 1$$

For each of the constraints $x' \le n - 1$ and $y' \le n-1$ respective complements, i.e., $x' \ge n$, $y' \ge n$:

$$N(P_x') = N(P_y') = \binom{2+(z'-n)-1}{z'-n} = z'-n+1 = z-n-1$$

And finally for the constraint $x' \ge n \land y'\ge n$:

$$N(P_x'P_y') = \binom{2+(z'-2n)-1}{z'-2n} = z'-2n+1 = z - 2n -1$$

But obviously I've messed up somewhere, because you will note that my inclusion-exclusion sum is zero, regardless of the values taken by $n$ and $z$.

I know from the generating function below that the answer will take the form $2n-z+1$ for $z>n$ and $z-1$ otherwise (alternately, $n - |z-n-1|$), but I do not know how to prove this is true in general. Note that the first case is equal to my first three terms in my inclusion/exclusion, and the second case is equal to the first term alone.

$$(\sum_{i=1}^n g^i)^2$$

I would like to understand how to do this with inclusion/exclusion.

$\endgroup$
0
$\begingroup$

The inclusion-exclusion sum is correct. It is simply the case that one should not always include all terms.

The term $N(P_x'P_y')$ will be zero for any $z\le 2n$ because the sum of two numbers $a,b>\frac{c}{2}$ must be greater than $c$. Thus we can eliminate that term since we are supposing $z \in [2,2n]$.

The second and third terms are also both zero if $z \le n$ because there is no way to add a number $a>n$ with a number $b>0$ and get $a+b\le n$.

So the trivial closed form must be expressed by cases:

$$ N(P_xP_y)=\begin{cases} z-1 & \quad z\in[2,n] \\ 2n−z+1 & \quad z\in(n,2n] \\ 0 & \quad \text{otherwise}\end{cases} $$

Showing that this is equivalent to $n−|z−n−1|$ on the range $z\in[2,2n]$ can be done by splitting the second equation into cases.

$$ n-|z-n-1| = \begin{cases} n+z-n-1 = z-1 \quad & 0 \ge z-n-1 \\ n-z+n+1 = 2n-z-1 \quad & 0 \lt z-n-1 \end{cases} $$

Now we show that $z\in[2,n]\implies 0\ge z-n-1$. Note the equation is maximized for fixed $n$ when $z$ is maximized, so we will take $z=n$.

$$0 \ge n-n-1=-1$$

Similarly, $z\in(n,2n]\implies 0<z-n-1$. The right hand size is minimized when $z$ is minimized, for fixed $n$. Since we are dealing in integers, this is equivlaent to $z\in[n+1,2n]$. So we take $z=n+1$ and find the condition is satisfied. Note the inequality is no longer strict because the (equivalent) interval we took was closed.

$$0 \le (n+1) - n - 1 = 0$$

$\endgroup$

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.