2
$\begingroup$

I am having problems analyzing the number of solutions to the equation of the form

$$x_1 + x_2 +x_3 +x_4 + x_5 +x_6 < 10$$

also if you can generalize the result and post some relevant links from where I can study i will be grateful. Thanks in advance.

  • 2
    Do you intend for the $x_i$ to be non-negative integers? If so, you should take a look at [Partition Numbers](http://en.wikipedia.org/wiki/Partition_(number_theory)).2011-11-29
  • 0
    yes xi >= 0 in every case well can't this problem be solved using combinatorics2011-11-29
  • 0
    See http://math.stackexchange.com/questions/9386/number-of-possible-solutions-for-an-equation and http://math.stackexchange.com/questions/40640/how-many-solutions-possible-for-the-equation-x-1x-2x-3x-4x-5-55-if2011-11-29

1 Answers 1

6

I will assume that we are looking for the number of ordered $6$-tuples with sum $<10$. So for example, the solution $x_1=6$, $x_2=x_3=x_4=0$, $x_5=2$, $x_6=0$ is to be considered different from the solution $x_1=2$, $x_2=x_3=x_4=0$, $x_5=6$, $x_6=0$.

You will find a very clear discussion of the ideas for a combinatorial solution in Wikipedia under Stars and Bars. Let $k$ and $n$ be fixed. The particular problems discussed there are (i) the number of solutions of $x_1+x_2+\cdots +x_k=n$ in positive integers and (ii) the number of solutions of $x_1+x_2+\cdots +x_k=n$ in non-negative integers.

There is no sense in my repeating here what is well done in an easily accessible source. However, your problem is somewhat different from the ones discussed in the Stars and Bars article.

Your condition is $x_1+x_2+\cdots +x_6<10$, so you are dealing with an inequality rather than an equation. But the inequality can be rewritten as $x_1+x_2+\cdots +x_6\le 9$. If you want to count the non-negative solutions of this inequality, that is the same as the number of non-negative solutions of the equation $x_1+x_2+\cdots +x_6+x_7=9$.

The above trick of dealing with $<$ by adding an extra variable works in general.

The number of positive solutions of $x_1+x_2+\cdots+x_k

We prove that this is the case by showing that there is a one-to-one correspondence between the positive solutions of the inequality and the positive solutions of the equation.

Given a solution $(a_1,a_2,\dots,a_k)$ of the inequality $x_1+x_2+\cdots+x_k

All positive solutions of $x_1+x_2+\cdots+x_k+x_{k+1}=n$ are obtainable in this way from a solution of the inequality $x_1+x_2+\cdots +x_k

We have exhibited an explicit bijection between the set of positive solutions of the inequality $x_1+x_2+\cdots+x_k

In a similar way, one can show that the number of non-negative solutions of $x_1+x_2+\cdots+x_knon-negative solutions of $x_1+x_2+\cdots +x_k+x_{k+1}=n-1$.

  • 0
    nicolas that is where I am getting confused why is there such a correspondence between the 2 equations2011-11-30
  • 0
    I expect you are referring to the fact that the number of solutions of an *inequality* is the same as the number of solutions of a related *equation*. I will add a proof to one of the assertions. It will take a few minutes.2011-11-30