Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
2  
Do you intend for the $x_i$ to be non-negative integers? If so, you should take a look at Partition Numbers. –  Austin Mohr Nov 29 '11 at 20:31
    
yes xi >= 0 in every case well can't this problem be solved using combinatorics –  AnkitSablok Nov 29 '11 at 20:33
    

1 Answer 1

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

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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