# Systematic approach to stars and bars with constraints between variables?

I was told to find the number of solutions $x_1+x_2+x_3+x_4=19$ under the constraints $x_1\neq x_2$ and $x_2\neq 2x_3$.

Let $A_1$ be the number of solutions under the constaint $x_1=x_2$ and $A_2$ under the constraint $x_2=2x_3$.

I think the answer is $\binom{22}{19}-|A_1\cup A_2|$. My idea was to calculate the second term using inclusion-exclusion. My problem is that my method of finding $|A_2|$ looks ugly to me, and even the calculation of $|A_1\cap A_2|$ was done "manually", which wouldn't work for many more variables...

For starters, let me describe what I did.

• For $A_1$ we have $2x_1+x_3+x_4=19$, so exactly one of $x_3,x_4$ is odd, and so we're really dealing with $y_1+y_2+y_3=9$. Thus $|A_1|=\binom{11}{9}$.
• For $A_1\cap A_2$ we have $5x_3+x_4=19$, and there are four solutions to this so $|A_1\cap A_2|=4$.
• For $A_2$ we have $x_1+3x_3+x_4=19$, i.e $(x_1+x_4)+3x_3=19$, so we can again count manually looking at $(x_1+x_4)$ as a single entity, and then check how many combinations work to make it. The solutions are $(16,1),(13,2),(10,3),(7,4),(4,5),(1,6)$ so $|A_2|=\binom{17}{16}+\binom{14}{13}+\binom{11}{10}+\binom{8}{7}+\binom{5}{4}+\binom{2}{1}$.

Thus the final answer is $$\binom{22}{19}-(\binom{11}{9}+\binom{17}{16}+\binom{14}{13}+\binom{11}{10}+\binom{8}{7}+\binom{5}{4}+\binom{2}{1}-4)$$

I'm guessing I have many mistakes, so I'd like to learn what they are, but also, how to systematically approach problems like these...

• $x_i$ are positive (or non-negative) integers? – leonbloy Sep 11 '16 at 13:40
• @leonbloy yes, they are, sorry. – combinarcotics Sep 11 '16 at 13:40