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.

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

share|improve this question

2 Answers 2

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.

share|improve this answer
    
Yes, please more help I am still baffled. –  Jack Forest Dec 5 '12 at 5:32
    
@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? –  Brian M. Scott Dec 5 '12 at 5:37
    
The number of solutions. –  Jack Forest Dec 5 '12 at 5:41
    
@Jack: Okay; hang on a bit while I add some explanation. –  Brian M. Scott Dec 5 '12 at 5:42
    
I'm sorry I just realized I made a mistake in the problem I didn't mean quadrupled I meant raised to the 4th power. –  Jack Forest Dec 5 '12 at 5:42

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

share|improve this answer

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.