Continued question from here.
With certain questions I have $x_i$ being constrained by various different inequalities, I want to know how to remove these from the problem, to bring me back to a straight forward application of the stars and bars method.
How can I convert a problem like:
$$\def\x{x_}\x1+\x2+\x3+\dots+x_i =15$$ with $\x1\leq3$
Back to a simple stars and bars problem such as $$y_1+\x2+\x3+\dots+x_i=33$$
How can I convert that bad $\x1$ into a nice $y_1$
$x_i,y_i\in\mathbb{Z^{\geq0}}$
I can see how to do it for $x_i \geq k$ since I can just take $y_a =x_a – k \geq 0$ and take $x_a = y_a +k$ and sub it into the original equation, which gives me some stars and some bars :).
Best Answer
I don't know if it can be done as a single S&B calculation but here are two S&B approaches:
(1) Do S&B for the equation without restriction. Subtract from that another S&B with restriction $x_1 \geq 4$.
(2) Do a separate S&B, omitting $x_1$ from the equation, for each of the four cases: $x_1 = 0,1,2,3$. Then sum the four results.
Example: Take $i=4$ so we have
$$\def\x{x_}\x1+\x2+\x3+x_4 =15\qquad\mbox{with }\x1\leq3$$
(1) S&B without restriction: we have $4-1 = 3$ bars and $15$ stars. #Ways= $\binom{18}{3}$.
S&B with $x_1 \geq 4$: we have $4-1=3$ bars and $11$ stars. #Ways = $\binom{14}{3}$.
TotalWays = $\binom{18}{3} - \binom{14}{3} = 452$.
(2) S&B with $x_1=0$: we have $3-1=2$ bars and $15$ stars. #Ways = $\binom{17}{2}$.
(The equation we have here is: $x_2+x_3+x_4 =15$.)
S&B with $x_1=1$: we have $3-1=2$ bars and $14$ stars. #Ways = $\binom{16}{2}$.
S&B with $x_1=2$: we have $3-1=2$ bars and $13$ stars. #Ways = $\binom{15}{2}$.
S&B with $x_1=3$: we have $3-1=2$ bars and $12$ stars. #Ways = $\binom{14}{2}$.
TotalWays = $\binom{17}{2} + \binom{16}{2} + \binom{15}{2} + \binom{14}{2} = 452$.