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.

$\endgroup$
6
$\begingroup$

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<n$ is the same as the number of positive solutions of $x_1+x_2+\cdots +x_k+x_{k+1}=n$.

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<n$, let $$a_{k+1}=n-(a_1+a_2+\cdots+a_k).\qquad\qquad(\ast)$$ Then $a_{k+1}$ is positive, and is completely determined by $(a_1,a_2,\dots, a_k)$. It is clear from $(\ast)$ that $a_1+a_2+\cdots+a_k+a_{k+1}=n$, so $(a_1,a_2,\dots, a_k,a_{k+1})$ is a positive solution of $x_1+x_2+\cdots +x_k+x_{k+1}=n$.

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<n$. For if $(a_1,a_2,\dots,a_k, a_{k+1})$ is a positive solution of $x_1+x_2+\cdots+x_k+x_{k+1}=n$, then $a_1+a_2+\cdots+a_k<n$, so $(a_1,a_2,\dots,a_k)$ is a positive solution of the inequality $x_1+x_2+\cdots+x_k<n$.

We have exhibited an explicit bijection between the set of positive solutions of the inequality $x_1+x_2+\cdots+x_k<n$ and the set of positive solutions of the equation $x_1+x_2+\cdots+x_k+x_{k+1}=n$. Thus the two sets have the same number of elements.

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

$\endgroup$
  • $\begingroup$ nicolas that is where I am getting confused why is there such a correspondence between the 2 equations $\endgroup$ – AnkitSablok Nov 30 '11 at 15:12
  • $\begingroup$ 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. $\endgroup$ – André Nicolas Nov 30 '11 at 15:26

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.