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$?
[Math] Ordered Quadruples Question
combinatorics
Related Solutions
This problem does not have an easy solution and has been explored quite deeply, resulting in some very fascinating results, but I won't go into those too much.
This is equivalent to asking for the number of ways to put $18$ indistinguishable objects into $4$ indistinguishable boxes (which is not easy to solve this way), or the total number of ways to partition $18$ into anywhere between $1$ and $4$ parts (less than $4$ parts implies empty boxes).
The main method I'm showing will be a recursive/summation calculation of the number of partitions, as it is in my opinion and to my knowledge the easiest to both derive and compute, and even this is pretty tedious.
Let $p(n)$ be the number partitions of $n$. Let the number of ways to partition $n$ into $k$ parts be $p_k(n)$.
Assuming you want $a$, $b$, $c$, and $d$ to be positive integers: $p_4(18)$
We can uniquely represent each group of different permutations of a particular quadruple by only counting the one that is ordered from largest to smallest. If we represent these as objects, we can draw diagrams for each partition. For example, this is the diagram for $9 = 4+3+2$: $$ \begin{align} \Box \Box \Box \Box \\ \Box \Box \Box \\ \Box \Box \end{align} $$
Since we're ordering the quadruples from largest to smallest, this means that no row in the diagram should be longer than the ones above it.
Partitioning a number into $k$ parts means we must have $k$ rows, so each row must have at least $1$. If we remove the first of each row, we have a bijection of the general partition of what is left constrained to those rows. In other words, $p_k(n) = \sum\limits_{i=1}^k p_i(n-k)$. Here's the diagram to demonstrate $p_3(9) = \sum\limits_{i=1}^3 p_i(6)$: $$ \begin{align} \Box \Box \Box \blacksquare \\ \Box \Box \blacksquare \\ \Box \blacksquare \end{align} $$
Assuming you want $a$, $b$, $c$, and $d$ to be non-negative integers: $\sum\limits_{i=1}^4 p_i(18) = p_4(22)$
We can break this down further by continuing to chop off these columns to get: $p_k(n) = \sum\limits_{r=1}^{{\lfloor}n/k{\rfloor}} \sum\limits_{i=1}^{k-1} p_i(n-rk)$.
Here are diagrams to visualize $p_3(9) = \sum\limits_{i=1}^2 \Big( p_i(6) + p_i(3) + p_i(0) \Big)$:
$$ \begin{align} \sum\limits_{i=1}^2 p_2(6): \Box \Box \Box \blacksquare \\ \Box \Box \Box \blacksquare \\ \blacksquare \\ \\ \sum\limits_{i=1}^2 p_2(3): \Box \Box \blacksquare \blacksquare \\ \Box \blacksquare \blacksquare \\ \blacksquare \blacksquare \\ \\ \sum\limits_{i=1}^2 p_2(0): \blacksquare \blacksquare \blacksquare \\ \blacksquare \blacksquare \blacksquare \\ \blacksquare \blacksquare \blacksquare \end{align} $$ Last couple of short optimizations: Obviously, $p_k(0) = 1$, $p_1(n) = 1$, $p_n(n) = 1$, and $p_k(n) = 0$ where $k > n$, and it's fairly trivial to show that $p_2(n) = \lfloor\frac{n}{2}\rfloor$.
The number of partitions of an integer $n$ into parts the largest of which is $k$ is equal to the number of partitions of $n$ into exactly $k$ parts. We can easily see this by simply tilting our head clockwise 90 degrees and forming a bijection. $k$ parts counts the rows, and the largest part having $k$ counts the columns.
We can now use what we know to break down $p_4(18)$.
$$ \begin{eqnarray*} p_4(18) &=& \sum\limits_{i=1}^3 \Big( p_i(14) + p_i(10) + p_i(6) + p_i(2) \Big) \\ \sum\limits_{i=1}^3 p_i(2) &=& 2 \\ \sum\limits_{i=1}^3 p_i(6) &=& p_1(6) + p_2(6) + p_3(6) = 1 + 3 + 3 = 7 \\ \sum\limits_{i=1}^3 p_i(10) &=& p_1(10) + p_2(10) + p_3(10) \\ &=& 1 + 5 + \sum\limits_{i=1}^2 \Big( p_i(7) + p_i(4) + p_i(1) \Big) = 6 + 4 + 3 + 1 = 14 \\ \sum\limits_{i=1}^3 p_i(14) &=& p_1(14) + p_2(14) + p_3(14) \\ &=& 1 + 7 + \sum\limits_{i=1}^2 \Big( p_2(11) + p_2(8) + p_2(5) + p_2(2) \Big) = 8 + 6 + 5 + 3 + 2 = 24 \\ p_4(18) &=& 24 + 14 + 7 + 2 = \boxed{47} \end{eqnarray*} $$
You can confirm my results here and read up more about partitions here.
I highly recommend reading through that wiki page, as well as writing a program to calculate these values for you if you have to do more than a couple of these.
EDIT: MJD just posted a very nice clean recursive function that is based off the exact same concept I demonstrated. Go use that if you can.
Part (a): read about stars and bars
$\binom{18+4-1}{4-1}$
Part (b)
$a=2p+1 , b=2q+1 , c=2r+1 , d=2s+1$
$p+q+r+s=7$
Stars and bars again
$\binom{7+4-1}{4-1}$
Part (c)
Continuing Brian’s solution, $a+10=w , b+10=x , c+10=y , d+10 = z$
$w+x+y+z=58$ where all four are at most 20.
Quadruples with at least one greater than 20:divide 37 into 4 and then add 21 to one of the four numbers
$\binom{37+4-1}{4-1}\times 4$
Quadruples with two greater than 20: divide 16 into 4 and then add 21 to two of the four numbers
$\binom{16+4-1}{4-1}\times\binom{4}{2}$
Last we use principle of inclusion and exclusion
$\binom{58+4-1}{4-1}-\binom{16+4-1}{4-1}\times 4 + \binom{16+4-1}{4-1}\times\binom{4}{2}$
Best Answer
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.
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.