# Extended Stars-and-Bars where the upper bound of a variable is one of the other variables

How many non-negative integer solutions are there for the equation x + y + z + w = 20, where x>y.

I started by substituting x for a new variable x'=x-y:
x > y
x-y > 0
x'>0

However, this led me to a point from which I didn't know how to make progress:
x'+ 2y + z + w = 20

How should I deal with the 2y?

• I'm not sure one can apply Stars-and-Bars with such modifications. In general introducing coefficients not equal to one makes the problem (counting non-negative integer solutions) more difficult. Would you entertain an alternative approach? – hardmath Apr 26 '19 at 23:53

By symmetry, the number of solutions with $$x>y$$ is the same as the number with $$x so the answer is "half the number of solutions where $$x\neq y$$." I would go about this by subtracting the solutions with $$x=y$$ from the total number of solutions.

Stars and bars gives the total solutions, so now we need to know the number of solutions to $$2x+w+z=20$$ in nonnegative integers. For a given $$x$$ this is just $$21-2x$$ so it's easy to add them up.

• Your logic makes perfect sense. Sadly, I feel it comes back to the problem I encountered in my attempt: not knowing how to make progress with Stars-and-Bars when 2 of the variables are the same. – pug Apr 27 '19 at 0:13
• @pug - saulspatz is saying this: iterate through $x=0,1,...,10$ and you have $w+z = 20-2x$ which is itself a stars-and-bars problem. however, this problem is so small ($2$ variables) that the no. of solutions is obviously ${20-2x + 2 -1 \choose 2 - 1} = 21 - 2x$ (he has a typo). so now you sum through all $x=0,1,...10$ etc – antkam Apr 27 '19 at 3:02
• @antkam Thanks for pointing out the typo. It's fixed. – saulspatz Apr 27 '19 at 11:14

$$x+y+z+w=20\tag{1}$$

Firstly it says $$x \gt y$$ so $$x=y+x'+1$$ where $$x'\ge 0$$.

This gives

$$x'+2y+z+w=19\, .$$

So since $$2y$$ is always even, $$x'+z+w$$ must be odd which means either all three variables are odd or just one is.

1. If all three are odd then say $$x'=2x''+1$$, $$z=2z''+1$$, $$w=2w''+1$$, giving

\begin{align}&& 2(x''+y+z''+w'')&=16\\[1ex] &\implies& x''+y+z''+w''&=8\, ,\end{align}

which has $$\binom{8+3}{3}$$ non-negative integer solutions by bars and stars.

1. If just one is odd, say $$x'=2x''+1$$, then the other two must be even: $$z=2z''$$, $$w=2w''$$, this gives

\begin{align}&& 2(x''+y+z''+w'')&=18\\[1ex] &\implies & x''+y+z''+w''&=9\, ,\end{align}

which has $$\binom{9+3}{3}$$ non-negative integer solutions by bars and stars. However, there are 3 choices for our odd variable so that's $$3\binom{9+3}{3}$$ total solutions for this case.

Adding both cases together we have a grand total of

$$\binom{8+3}{3}+3\binom{9+3}{3}=825\tag{Answer}$$

non-negative integer solutions to $$(1)$$ with $$x\gt y$$.

• A nice approach. However, the equation $x'' + y + z'' + w'' = 8$ has only $\binom{\color{red}{8} + 3}{3}$ solutions in the nonnegative integers. – N. F. Taussig Apr 27 '19 at 9:09
• Whoops! Thank you @N.F.Taussig. Where was my head when I wrote that? I don't know. I'll edit. – N. Shales Apr 27 '19 at 9:35