# How to convert a problem to a stars and bars problem?

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 :).

• (I write $\mathbb{Z}^{\geq 0}$.) Also, for the example problem, it would be possible to do a stars-and-bars problem separately for each $x_1 \in \{0,1,2,3\}$. – Rebecca J. Stones Aug 28 '14 at 3:41
• But I imagine I can do some change of variable to make it into a new sum? Thank you for that notation, good idea! – Partly Putrid Pile of Pus Aug 28 '14 at 3:41
• is there infinite $x_i$ ? – idm Aug 28 '14 at 8:53
• @idm No sorry, there is an arbitrary number of bars. I will edit. – Partly Putrid Pile of Pus Aug 28 '14 at 8:57
• Impressive. This is the 1000th question in the examples-counterexamples tag. (Which incidentally, gave me the Taxonomist badge back when it had reached 50 questions.) – Asaf Karagila Aug 28 '14 at 8:59

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$.

• Thank you for this detailed answer. Very helpful! – Partly Putrid Pile of Pus Sep 23 '14 at 7:34