1
$\begingroup$

How many Positive integer solutions does the equation $x + y + z + w = 15$ have?

Attempt:

Let $x = m + 1, y = n + 1, z = o + 1, w = p + 1 $

Then, $ m + 1 + n + 1 + o + 1 + p + 1 = 15$

$ m + n + o + p = 11 $

$\endgroup$
  • 1
    $\begingroup$ Do you see is there any point in changing variables from $x,y,z,w$ to $m,n,o,p$... that may not be considered as an attempt... $\endgroup$ – user87543 Dec 11 '13 at 9:19
  • 2
    $\begingroup$ You are correct that the number of positive solutions to $x+y+z+w=15$ is the same as the number of nonnegative solutions to $m+n+o+p=11.$ To count solutions to the latter, imagine dividing the sequence $$***********$$ into four (possibly empty) groups by placing three separator marks somewhere in the sequence. So for example, $$ ***\mid **\mid\mid ****** $$ would correspond to the solution $3+2+0+6.$ Now you just have to enumerate such sequences. $\endgroup$ – Will Orrick Dec 11 '13 at 10:08
5
$\begingroup$

From your attempt we know that this problem is equivalent to the number of non-negative integer solutions to $m + n + o + p = 11$, which is far simpler. This type of problem is sometimes known as "Stars and Bars" http://en.wikipedia.org/wiki/Stars_and_bars_%28combinatorics%29. The idea is that you have 11 "stars", how many different ways can you put 3 bars in between them to separate them into 4 groups? In total, you have $11 + 4 - 1 = 14$ spaces for either a star or a bar, from that you need to choose $4 - 1 = 3$ spaces to place a bar. This equates to $\binom{14}{3} = 364$.

$\endgroup$
2
$\begingroup$

Here is my try.

Your equation is $x+y+z+w=(x+y)+(z+w)=15$. First we see $x+y$ and $z+w$ as two unknowns, that is $a+b=15$ and $a,b$ satisfy $2\leq a,b\leq13$. Easily, we can say that there are $12$ positive integer solutions for $a$ and $b$. Then we will see there are how many postive integer solutions for $x+y=a$ and $w+z=b$. We note the number of such solutions as $N(\cdot)$.

If $a=2$, then $b=13$. We see that $a=2=x+y$ has unique $1$ solutions for $x$ and $y$, that is $x=1$ and $y=1$. $b=13=z+w$ has $12$ solutions for $z$ and $w$, that is $z=1,2,\dots,12$ and $w=12,11,\dots,1$. Then there are $N(a=2)*N(b=13)=1*12=12$ solutions for $a=2$ and $b=13$.

Then we do like this, we can make a list of the 12 solutions for $a$ and $b$: $$N(a=2)=1\Leftrightarrow N(b=13)=12\Leftrightarrow N(a=2,b=13)=1*12$$ $$N(a=3)=2\Leftrightarrow N(b=12)=11\Leftrightarrow N(a=3,b=12)=2*11$$ $$\vdots$$ $$N(a=13)=12\Leftrightarrow N(b=2)=1\Leftrightarrow N(a=3,b=12)=12*1$$ So the number of all the solutions is $$N(x+y+z+w=15)=\sum_{n=1}^{12}n*(13-n)=364.$$

$\endgroup$
  • $\begingroup$ This sounds very intuitive.. I could not check all $N(a)$ of what you have written but I feel if this question is to be solved then this should be the best way.. well done :) $\endgroup$ – user87543 Dec 11 '13 at 9:55
  • $\begingroup$ I tested this problem with Matlab and the result is just like what I got with pen. $\endgroup$ – Martial Dec 11 '13 at 9:58
  • 1
    $\begingroup$ The total number of partitions of $15$ is $176$. Not all of them slice the number into four distinct positive parts. So the answer should be less than that. You probably made the mistake of counting different permutations as different solutions. Then again, the OP did not specify whether order is important or not. $\endgroup$ – Lucian Dec 11 '13 at 10:20
  • $\begingroup$ @Lucian: I don't see where it says that $x,$ $y,$ $z,$ and $w$ have to be distinct. Also, it's evident that order does matter. Asking for positive integer solutions to $x+y+z+w=15$ is an unambiguous question. $\endgroup$ – Will Orrick Dec 11 '13 at 10:26
  • $\begingroup$ They're not distinct. Otherwise the number would further decrease to only $27$. $\endgroup$ – Lucian Dec 11 '13 at 10:36
2
$\begingroup$

Hint:

Find the coefficient of $x^{15}$ of the following function:

$$f(x)=(x+x^2+x^3+\cdots+x^{15})^4$$

Why this gives you the number of integer solution of your equation?

$\endgroup$
  • $\begingroup$ Down-voter, is it wrong? $\endgroup$ – Salech Rubenstein Dec 11 '13 at 9:32
  • $\begingroup$ I have down voted this.. I see no point in making the answer so complicated... i do not think this would be a good idea.. $\endgroup$ – user87543 Dec 11 '13 at 9:34
  • $\begingroup$ I do not prefer to be rude but then i see no point... One more thing is i can not take back my down vote unless it is edited... :O $\endgroup$ – user87543 Dec 11 '13 at 9:37
  • $\begingroup$ Did I asked you to take back your down vote? $\endgroup$ – Salech Rubenstein Dec 11 '13 at 9:39
  • $\begingroup$ I said i can not take back my down vote unless it is edited.. If you have decided to be rude It is up to you... $\endgroup$ – user87543 Dec 11 '13 at 9:41
2
$\begingroup$

There is a formula for the number of solutions in $N^p$ of the equation $x_1+ ... +x_p=n$, notably $C_{n+p-1}^{p-1}$.

$\endgroup$
  • $\begingroup$ How can we derive the formula $\endgroup$ – Koolman Nov 27 '16 at 17:50
  • $\begingroup$ @Koolman You can look at it as having n spaces that can be either 1 or 0. We will add 3 0s in any of the spots where the spaces before the first 0 is $x_1$ and the space after the first 0 is the next digit, and so forth. So we have n spaces with (p -1) zeros anywhere in it. Since we took (p-1) spaces off the n total, we will add (p-1) to n. So we have (n+p-1). Now you can say, how many ways can we arrange the 1s and 0s in the (n+p-1) spaces where there are (p-1) zeros? So you get (n+p-1) choose (p-1). $\endgroup$ – Jose Ramirez Dec 11 '17 at 7:32
  • $\begingroup$ The above is derived for non-negative values. $\endgroup$ – Jose Ramirez Dec 11 '17 at 7:43
  • $\begingroup$ @JozemiteApps Yes , I got confused if it is derived for positive numbers or non-negative numbers . $\endgroup$ – Koolman Dec 11 '17 at 14:03
0
$\begingroup$

A visual solution I learned from my teacher was using spaces (to make it easier to understand the math). Since the total is 15, we have 15 spaces. BUT, because we are using positive numbers (not non-negative), then we have to add 1 more to each variable (to make it positive if it were to be 0), which means we subtract how much we added from the total. So we have 11 spaces.

_ _ _ _ _ _ _ _ _ _ _

Since we have 4 variables, we add (4-1) zeros to separate the spaces into 4 sections.

_ _ 0 _ _ 0 _ _ 0 _ _

Since the zeros took 3 spaces, we add 3 spaces wherever you want.

_ _ _ 0 _ _ 0 _ _ _ 0 _ _ _

Notice that for the above spaces, we have 3 + 2 + 3 + 3 = 11. That is 1 solution, but we can't keep doing that. It's not efficient. So here we can use the total number of spaces, 14, and partition it into 4 sections, so we have:

(p + n - 1) choose (n - 1) => (11 + 4 - 1) choose (4 - 1) => (14 choose 3) = 364.

Where p is the total of the equation and n is the number of variables. Notice that the above equation is the visual I used. Same thing.

$\endgroup$

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.