Integer solutions using stars and bars with bounds on integers

143 Views Asked by At

In this page of brilliant , an example problem is as follows

$$\sum_{i=0}^6 a_i \leq 100$$ How many positive integers $(a_1,a_2...,a_6)$ with $ i \leq a_i$ for $i=1,2,3,4,5,6$ satisfy the sum?

In the solution they start of with introducing an extra variable $c$ into the equation making it:

$$ c+ \sum_{i=0}^6 a_i \leq 100$$

With, $ 0 \leq c$

But I don't understand why? They call this addition of 'c' is some kind of bijection but I'm not sure what purpose it is serving..

1

There are 1 best solutions below

1
On BEST ANSWER

The term $c$ has been introduced to the expression as a dummy variable, which saves you a lot of work in the long run.

Via the introduction of this new dummy variable '$c$', the below problem has been transformed from $$\sum_{i=0}^6 a_i \leq 100$$ to $$\sum_{i=0}^6 a_i + c = 100$$

Why this works out so well is that each non-negative value taken up by this dummy variable $c$ corresponds to a particular case of the inequality. For example, when $c=10$, $\sum_{i=0}^6 a_i = 90$. To reiterate, taking this extra variable saves you the effort of having to calculate so many different cases.

The number of positive integral solutions of the above equation can be calculated easily via the well known formula for the same. I think you can take it from here!