How many non-ordered quadruples satisfy $a+b+c+d=18$?
I know how to do this if this is ordered quadruples, but in non-ordered quadruples $(1,1,1,15)$ is the same as $(15,1,1,1)$ so you have to account for overcounting. However, you cannot simply divide by $4$! because there are different number of repeated elements in each case. So I am not sure how to proceed.
Best Answer
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.