Stars and Bars question with restriction that two variables must be equal

690 Views Asked by At

How would one proceed in their thought process when trying to solve what appears to be a standard stars and bars equation, with $x_i\geqslant$ 0, e.g.

$$x_1+x_2+x_3+x_4=24$$

Except, let's say that there is a restriction that two of the variables must be equal. We can write the equation as such:

$$x_1+x_2+2x_3=24$$

At first, I tried substituting $2x_3$ with $y$, and solving for

$$x_1+x_2+y=24$$

using the standard stars and bars method. However, that would result in over counting, because it does not account for restrictions on $y$, since $y$ has to be even.

Any suggestions on how to solve this sort of problem?

EDIT:

I realize that you can solve smaller numbers using cases, but what would be the approach if you had larger numbers (making it impractical to use cases)? e.g. $$x_1+x_2+x_3+x_4+2x_5=350$$

1

There are 1 best solutions below

1
On

If the two identical variables are equal to $x$, the rest of the sum is $n=24-2x$. You can pick positions of the two identical variables in ${4 \choose 2 }$ different ways.

Now, you have to split $n$ between the two remaining variables and there are ($n+1=25-2x$) ways to do it in general but you have to be careful. Not all splits are valid.

Take for example $x=0$. You cannot choose (12, 12), (0,24) and (24,0) for the last two variable values because you will end up with two many identical variables. The same is true for $x=1,2,3,4,5,7,8$. In these cases you will have $n+1-3=22-2x$ available pairs for the last two variables.

Take now $x=6$ for example. There is only one pair of values that has to be avoided as values of the last two variables: (6,6). The same is true for $x=9,10,11$ (you can easily check that). In these cases you have exactly $n=24-2x$ choices to split $n$ between the last two variables.

You can drop $x=12$ because it leads to 12+12+0+0 which is illegal.

Possible values for $x$ are therefore 0, 1,2, ...,11. For each value of $x$ you can put two identical variables in ${4 \choose 2 }$ different places. So that factor multiplies everything. For every single value of $x$ you have either $(22-2x)$ or $(24-2x)$ways to set the remaining two variables. So the final result is:

$$\binom{4}{2}\times\left(\sum_{x\in\{0,1,2,3,4,5,7,8\}}(22-2x)+\sum_{x\in\{6,9,10,11\}}(24-2x)\right)=$$

$$6\times\left(4\times2+\sum_{x=0}^{11}(22-2x)\right)=$$

$$6\times\left(8+12\times22-2\sum_{x=0}^{11}x\right)=6\times(8+12\times22-2\times66)=840$$