How do we find the number of nonnegative integer solutions of the inequality:
$$x_1 + x_2 + \cdots + x_6 < 10\text{ ?}$$
Answer is $5005$, can someone elaborate and show me the steps required to solve this discrete math problem?
Asked
Active
Viewed 439 times
1
-
1http://math.stackexchange.com/questions/92194/number-of-nonnegative-integral-solutions-of-x-1-x-2-cdots-x-k-n?rq=1 – rlartiga May 25 '14 at 19:55
-
@FlybyNight in the original post without edit are $x_6$ variables – rlartiga May 25 '14 at 19:58
-
@rlartiga Thanks – Fly by Night May 25 '14 at 20:00
-
@FlybyNight : It looked like a typo to me: x+6 appeared where x_6 was intended. The two keys are adjacent on keyboards in the USA. – Michael Hardy May 25 '14 at 20:00
-
@MichaelHardy The "typo" had been made by someone that edited the OP. – Fly by Night May 25 '14 at 20:02
-
So how would we go about solving this? – Ash May 25 '14 at 20:07
-
The first thing I notice about this is that $5005$ is a binomial coefficient: $\dbinom{15}6 = 5005$. ${}\qquad{}$ – Michael Hardy May 25 '14 at 20:12
-
I solved it in another post. – Felix Marin May 30 '14 at 06:47
4 Answers
3
We have $9$ identical candies, and there are $6$ kids wanting candy. How many ways are there to distribute $9$ or fewer candies between the $6$ kids?
Equivalently, imagine that there is a $7$-th kid who will get any lefover candies. The number of ways to give out $9$ or fewer candies to $6$ kids, with some possibly getting $0$ candies, is the number of ways to distribute $9$ candies among $7$ kids.
This is a standard Stars and Bars problem that you are likely familiar with, perhaps in the less sweet form of counting the solutions of $x_1+x_2+\cdots +x_7=9$.
André Nicolas
- 507,029
-
Please go into more detail about the 7th kid, why are we all of a sudden adding another x to the equation? – Ash May 25 '14 at 20:25
-
Because counting the solutions of the inequality $x_1+\cdots +x_6\le 9$ is the same as counting the solutions of the equality $x_1+\cdots +x_6+x_7=9$. The solutions with $x_7=0$ give us the solutions of $x_1+\cdots +c_6=9$, the solutions with $x_7=1$ give us the solutions with $x_1+\cdots +x_6=8$, and so on. – André Nicolas May 25 '14 at 20:29
-
FACEPALM -_-...... Sorry for asking the obvious. I must have been over thinking this. – Ash May 25 '14 at 20:39
-
1
HINT
Imagine the $x_1,x_2,\ldots,x_6$ as letter boxes that you have to put letters into.
Let $x_7$ be a bin, where the letters you post don't count for anything.
You have nine letters to post and seven boxes to post them in.
If you put all nine in $x_7$ then $x_1+x_2+\cdots+x_6=0$.
If you put eight in $x_7$ then $x_1+x_2+\cdots+x_6=1$.
If you put seven in $x_7$ then $x_1+x_2+\cdots+x_6=2$.
How many ways are there of posting nine letters in seven boxes, when order doesn't matter?
Fly by Night
- 32,272
-
-
@Ash Instead of counting all of the cases separately, you can include an $x_7$. You can think of the $x_7$ as a bin, or as your pocket. If you have $x_1+\cdots+x_6=0$ then you have not posted a single letter into any of the postboxes $x_1,\ldots,x_6$; they are all in your pocket. If $x_1+\cdots+x_6=1$ then you have posted a single letter; all-but-one are in your pocket. You can count all cases, i.e. $=0$, $=1$, $=2$, etc, by including your pocket in the counting. You have nine letters to post (or not post) – Fly by Night May 25 '14 at 20:35
0
Suppose we wanted to know the number of integer solutions of $x_1 + x_2 + ... + x_n = k$. This is equivalent to the combinatorics question "How many ways are there to distribute $k$ indistinguishable balls into $n$ distinguishable boxes?". It is a well-known combinatorics theorem that the answer to this question is $\binom{n+k-1}{k}$.
Therefore, the total number of solutions is going to have to take into account the number of possibilities for $0$ balls, $1$ ball, and so forth up to $9$. Thus, the following expression gives us what we want:
$$\sum_{k = 0}^9 \binom{k + 5}{k}$$
Kaj Hansen
- 33,011