# Philosophy of adding extra term in combinatorics question If x 1 </msub> +

Philosophy of adding extra term in combinatorics question
If ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}\le 20$ where ${x}_{1},{x}_{2},{x}_{3},{x}_{4}$ are non negative integers , then how many possible outcome are there ?
It is basic counting problem, we solve it by adding an extra non-negative integer such that ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}+{x}_{5}=20$, and then use star and bars . Hence the answer is $\left(\genfrac{}{}{0}{}{20+5-1}{20}\right)$.
However , there is something that stuck in my mind such that why are we adding only one extra variable ${x}_{5}$, to be clearer , why dont we add more than one extra variable. For example , why did not i find the solution of ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}+{x}_{5}+{x}_{6}=20$ where the extra terms ${x}_{5}$ and ${x}_{6}$ are non-negative, too. Briefly, why did we restrict ourselved with only one extra variable? Can you enlighten me ?
You can still ask an expert for help

## Want to know more about Discrete math?

• Questions are typically answered in as fast as 30 minutes

Solve your problem for the price of one coffee

• Math expert for every subject
• Pay only if we can solve it

America Barrera
Step 1
Stars and bars work for $\sum _{i=1}^{k}{x}_{i}=n,{x}_{i}\in \left\{0,1,2\dots \right\}$ because we only need $k-1$ bars to separate k groups of x. Hence, we consider n stars and $k-1$ bars to obtain $\left(\genfrac{}{}{0}{}{n+k-1}{n}\right)$ ways to place the stars, while the bars fill the rest of the positions.
${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}=m\le 20$ is another way of saying place the 4th bar in the m+4th position. We need the 4th bar because there is at least one group remaining.
Step 2
For example ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}=12\le 20$ means in the first 16 positions we placed 12 stars and 4 bars. It happens that if we have simply have 5 groups, the remaining stars are forced into place, so the set of (${x}_{1}$, ${x}_{2}$, ${x}_{3}$, ${x}_{4}$) forms an one-to-one and onto relation with the set of solutions of ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}+{x}_{5}=20$. This means we can use stars and bars for the second problem as the answer would be the same as the first. If additional groups and bars (or variables) are introduced, we get instead an one-to-many relationship so we are unable to immediately take advantage of stars and bars.

Step 1
Because we want to consider unique cases. Using more than one variable overcounts. For example, if you took ${x}_{5}$ and ${x}_{6}$ such that ${x}_{1}+{x}_{2}+{x}_{3}+{x}_{4}+{x}_{5}+{x}_{6}=20$.
Say we have ${x}_{1}=1$, ${x}_{2}=5$, ${x}_{3}=7$, ${x}_{4}=2$. Then, this is a solution to our original inequality. With our new equation we formed, this would mean that in this one case, we are actually counting the same case six times, as stars and bars would count $\left({x}_{5},{x}_{6}\right)$ to be (0,5), (1,4), (2,3), (3,2), (4,1) and (5,0). That's why we take one variable so we don't count duplicates.