# Simple Counting Question

How many solutions to the equation $x_1 + x_2 + x_3 = 11$ for positive integers, are there??

-
One way is to fix $x_1$ to $1, 2, \ldots, 9$ (why $9$?). How many solutions are there in $x_2, x_3$ for $x_2 + x_3 = 11-x_1$? You can simply enumerate these $9$ numbers and add. (There's also a formula, I am sure someone else will post it.) –  Srivatsan Sep 6 '11 at 15:28
The answer is 10C2 , or " 10 choose 2". You put 11 objects side-by-side, and then you need to figure out the number of ways of partitioning the collection into three different parts $x1,x_2,x_3$. One way of doing this is by putting "dividers" after a given object to indicate the numbers $x_i$. There are 10 spaces from which you can choose the dividers, and 2 dividers (I, personally am a uniter, not a divider) to be chosen, since once $x_1,x_2$ are known, $x_3$ is uniquely determined. –  gary Sep 6 '11 at 15:35
A far more interesting problem is to find number of positive integer solution of $x_1 + x_2 + x_3 = 11$ where $0 \lt x_1 \lt x_2 \lt x_3$. –  Quixotic Sep 6 '11 at 18:34

Consider your question as if you have 11 sites, and you have to put 2 barriers that would split those sites into 3 groups.

Your constraint is that x1,x2,x3 should be positive, i.e. 0 is not a valid value. Means you may not put 2 barriers at the same joint. Also the barrier may not be put at the end. This leads to the following:

• There're 11-1 = 10 allowed joints (places where barriers may be put)
• Two barriers may not occupy the same joint
• Barriers are indistinguishable (means - putting barriers at a,b and b,a is the same).

Hence the answer is C (11-1) over (3-1). Which is (11-1)! / [ (11-3)! * (3-1)! ] = 45

-
@Thijs Laarhoven: I confused multiplication with division. I meant (11−1)!/(11−3)!/(3−1)! Which is 45. Hence - means it's a standard combinatorial question of choosing M elements from N. –  valdo Sep 6 '11 at 16:02

This is purely a Question based upon the combinations and permutations, let me try.

In general we have the standard result $x_1+x_2+.......x_n=k\:$ then number of positive integer solutions is given by $(n+k-1)_{\large C_{k}}$ so according to your question it's $(3+11-1)_{\large C_{11}}$ which is $13_{\large C_{11}}=78$.

I hope I have put forward what I knew, I hope that it's correct, but leave it to scholars of this site to decide whether it's correct or not.

-
if you want further explanation ask me,so that i can give how can we prove the theorem and so on,as i tried many results out of it, –  Iyengar Sep 6 '11 at 15:38
Your answer would be true iff 0 would be a valid value for x1,x2,x3. Otherwise the answer is 45. –  valdo Sep 6 '11 at 15:42
yes sir you are true,i answered for the non-negative integers ,but if you restrict to only positive integers its what you said which is right –  Iyengar Sep 6 '11 at 15:51

This is one of the "balls in boxes" problems; you have a collection of k empty boxes in which you want to put n objects. Let's do first the more general case where boxes may be empty (i.e., $x_i=0$ is allowed) , and then we can do your case where $x_i>0$.

So, this is a method used: we put all n objects and k boxes side-by-side. Then the idea is that every partition of these (k+n) objects into (k-1) parts is a sum $x_1+x_2+...+x_k=n$ (by partition, we mean that we put a total of k dividers after certain of the objects and boxes). How so? If we put , say, the 1st divider after box $x_i$, that is used to mean that we put a total of i objects in the 1st box; if we put the second divider at place j , then that means that there are (j-i) objects in the second box, and so on. So for any assignment of dividers, we have an assignment $x_1,x_2,...,x_k$, with $x_1+x_2+...+x_k=n$. That gives us a total of ${n+k-1} \choose {k-1}$ possible assignments; note we use k-1 instead of k, because once we have chosen k-1 dividers, the number of objects for the $k$th box is just given by all the objects that are left.

Now, let's consider the case where $x_i>0$. We then throw an object into each of the boxes (for a total of k objects we are throwing in) , so that we have a total of $n+k-1-k=n-1$ places left, to make sure no box is empty, and then we "recur" , by using the method above, i.e., we now find all solutions to $x_1+....+x_k=n-k$ , and we get ${n-1}\choose {k-1}$.

As a small example, take 4 objects to be put into 3 boxes. We then lay out in a line, the 3 objects , followed by the three boxes. Notice that if you put dividers behind objects ,say, 1 ,2,3 respectively . This is then the combination $x_1=x_2=x_3=1$

-
My Apologies: I don't know how to do the Tex for "n choose k", and every time I right-click on one, I get a blank dialogue box, for some reason. –  gary Sep 6 '11 at 16:15
Iyengar, it comes out as $n_{c_{k}}$ ; I was hoping for the "fraction form" without the middle line. –  gary Sep 6 '11 at 16:34
Thanks, Srivatsan. –  gary Sep 6 '11 at 17:00
By the way, one tip to learn such $\TeX$ tricks and symbols. Notice that Thijs's answer uses the notation you want to use. So clicking on "edit" at the bottom of his answer will give you the entire answer in editable form. In particular, you will find the $\TeX$ code for $\binom{n}{k}$; for e.g., he seems to use the $\binom$ command. –  Srivatsan Sep 6 '11 at 17:08
@Srivatsan: There's an even simpler way: right click on a formula and choose "show source". –  t.b. Sep 6 '11 at 17:56

The first exercise of the first section of the first chapter of the first volume of George Pólya and Gábor Szegő's masterpiece does it this way: for every positive integers $a_k$ and every nonnegative integer $b$, the number of nonnegative integer solutions of the equation $a_1x_1+\cdots+a_nx_n=b$ is the coefficient of $t^b$ in the series $$s(t)=\prod_{k=1}^n\frac1{1-t^{a_k}}.$$ The proof is by inspection once one notes that, for every positive integer $a$, $$\frac1{1-t^{a}}=\sum\limits_{x=0}^{+\infty}t^{ax}.$$ Hence the product which defines $s(t)$ is $$s(t)=\prod_{k=1}^n\sum\limits_{x_k=0}^{+\infty}t^{a_kx_k}=\sum\limits_{x_1,\ldots,x_n}t^{a_1x_1+\cdots+a_nx_n},$$ and the coefficient of $x^b$ is the number of ways of writing $b$ as a sum $a_1x_1+\cdots+a_nx_n$.

You are looking at the case $n=3$, $a_1=a_2=a_3=1$ and $b=11-3=8$ hence looking for the coefficient of $t^8$ in the series $$s(t)=\frac1{(1-t)^3}=\frac12\frac{\text{d}^2}{\text{d}t^2}\frac1{1-t} =\frac12\frac{\text{d}^2}{\text{d}t^2}\sum\limits_{k=0}^{+\infty}t^k=\frac12\sum\limits_{k=0}^{+\infty}(k+2)(k+1)t^k,$$ hence the answer is $\frac12(8+2)(8+1)=45$.

-
+1 for the first sentence :) –  t.b. Sep 6 '11 at 17:53
@Theo: Yes, this bon mot was a huge motivation to write the answer... :-) –  Did Sep 6 '11 at 17:56
I said simply counting question -- that answer is way over my head. lol –  user10695 Sep 6 '11 at 23:25
@user, what part is way over your head? To use some series? –  Did Sep 6 '11 at 23:59
Well, it happens that data structures and generating functions ARE intimately related. What were the subjects taught in your class? –  Did Sep 7 '11 at 0:52