How many ordered quadruples $(x_1,x_2,x_3,x_4)$ that are elements of the $\Bbb N^4$ are there such that $x_1+x_2+x_3+x_4\le 50$?
Ordered Quadruples Question
2 Answers
This is almost a standard stars-and-bars problem. To make it one, add a fifth variable, $x_5$, and count the solutions to $x_1+x_2+x_3+x_4+x_5=50$ in non-negative integers: each solution to your problem corresponds to exactly one solution to the modified problem and vice versa, so the two problems have the same number of solutions. The Wikipedia article to which I’ve linked has a pretty good explanation of how to solve this modified problem, but if you need more help, just leave a comment.
Added: Imagine that I have $50$ identical balls, and I want to put them into $5$ numbered bins. Let $x_1$ be the number of balls that I put into Bin $1$, $x_2$ the number that I put into Bin $2$, and so on. Then each possible distribution of the balls is completely described by a solution to the equation
$$x_1+x_2+x_3+x_4+x_5=50\;,\tag{1}$$
and each solution to $(1)$ describes a possible distribution of the balls amongst the bins. Now I can picture a distribution of balls by arranging all $50$ balls in a line and thinking of the first $x_1$ balls as the contents of Bin $1$, the next $x_2$ balls as the contents of Bin $2$, and so on; I’ll just put down four markers to show where the balls in one bin leave off and those in the next bin begin.
For example, if there were only $10$ balls, I might picture the distribution that has $3$ balls in Bin $1$, none in Bin $2$, $6$ in Bin $3$, $1$ in Bin $4$, and none in Bin $5$ as
ooo||oooooo|o|; this also corresponds to the solution $3+0+6+1+0=10$ to the equation $x_1+x_2+x_3+x_4+x_5=10$.
Each of these pictures is then a string of $54$ objects, $50$ balls and $4$ markers. We can put the $4$ markers anywhere in the string, and once they’re in place, the whole string is known: every other position is occupied by a ball. There are $\binom{54}4$ ways to choose $4$ of the $54$ positions in the string, so there are $\binom{54}4$ distributions of the balls and hence $\binom{54}4$ solutions to $(1)$ in non-negative integers.
-
0Yes, please more help I am still baffled. – 2012-12-05
-
0@Jack: So that I know what to write: is it the connection between the two problems, or is it the calculation of the number of solutions to the second equation? – 2012-12-05
-
0The number of solutions. – 2012-12-05
-
0@Jack: Okay; hang on a bit while I add some explanation. – 2012-12-05
-
0I'm sorry I just realized I made a mistake in the problem I didn't mean quadrupled I meant raised to the 4th power. – 2012-12-05
-
0@Jack: I knew what you meant; I was going to mention it later, when I got round to editing the question to insert $\LaTeX$. – 2012-12-05
-
0Thank you that was very helpful. How does the answer change when you consider <= 50 instead of = 50 and is the answer the same whether you have 4 or 5 x's? – 2012-12-05
-
0@Jack: The number of solutions in non-negative integers to $x_1+\ldots+x_n\le m$ is the same as the number of solutions in non-neg. ints. to $x_1+\ldots+x_n+x_{n+1}=m$; the extra variable takes up the slack in the inequality. – 2012-12-05
-
0Ok I think I understand thank you very much, just to be clear x1+x2+x3+x4<=50 is the same as x1+x2+x3+x4+x5=50? – 2012-12-05
-
0@Jack: Yes. Each solution to the inequality corresponds to a unique solution to the equation: $x_5$ is simply the difference between $50$ and $x_1+x_2+x_3+x_4$. Conversely, each solution to the equation gives you a solution to the inequality just by throwing away $x_5$. The two sets of solutions are thus in one-to-one correspondence. – 2012-12-05
-
0I reread all of this when I woke up this morning and now I believe that I do understand the question and the answer, does the fact that it is asking about the set of natural numbers raised to the fourth not matter? – 2012-12-05
-
0@Jack: It just tells you that you’re looking at an inequality involving a sum of $4$ natural numbers. Had the problem asked for the number of $\langle x_1,\dots,x_8\rangle\in\Bbb N^8$ with $x_1+\ldots+x_8\le345$, we’d have used the same method: this is the same as the number of solutions in non-neg. ints. to $x_1+\ldots+x_8+x_9=345$, which is $\binom{345+9-1}{9-1}=\binom{353}8\approx 5.52\times 10^{15}$. – 2012-12-05
It is not clear what "the set of natural numbers quadrupled" means, it sounds like the multiples of $4$. We will assume that by natural number, an integer $\ge 1$ is meant. (To someone in logic, it would likely mean non-negative integer.)
Under the above interpretations, we want to count quadruples $(4y_1, 4y_2,4y_3,4y_4)$ that have sum $\le 50$, so quadruples $(y_1,y_2,y_3,y_4)$ such that $y_1+y_2+y_3+y_4 \le 12$.
Use the suggestion of Brian M. Scott, and count the quintuples $(y_1,y_2,y_3,y_4,y_5)$ such that $y_1+y_2+y_3+y_4+y_5=13$. This is the distribution of $13$ identical candies to $5$ kids problem, with every kid getting at least one candy. By standard Stars and Bars, the number of ways is $\dbinom{12}{4}$.