1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (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\}$. $\endgroup$ – Rebecca J. Stones Aug 28 '14 at 3:41
  • $\begingroup$ But I imagine I can do some change of variable to make it into a new sum? Thank you for that notation, good idea! $\endgroup$ – Partly Putrid Pile of Pus Aug 28 '14 at 3:41
  • $\begingroup$ is there infinite $x_i$ ? $\endgroup$ – idm Aug 28 '14 at 8:53
  • $\begingroup$ @idm No sorry, there is an arbitrary number of bars. I will edit. $\endgroup$ – Partly Putrid Pile of Pus Aug 28 '14 at 8:57
  • $\begingroup$ 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.) $\endgroup$ – Asaf Karagila Aug 28 '14 at 8:59
1
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.