In how many ways can $18$ be written as the sum of four distinct positive integers?

Question

In how many ways can $18$ be written as the sum of four distinct positive integers? Note: $1 + 3 + 5 + 9$ and $5 + 1 + 3 + 9$ are counted as different ways

---

Other than just bashing it out, how can I do this in a reasonable amount of time where I won't miss anything?

Answer 1

Honestly, the best way is casework on the biggest number.

The biggest number must be $12$ or under, because if otherwise it would be impossible.

• Biggest no = 12, there is one quadruple, namely $12, 3, 2, 1$.
• Biggest no = 11, there is one quadruple, namely $11, 4, 2, 1$.
• Biggest no = 10, there are two quadruples, namely $10, 5, 2, 1$ and $10, 4, 3, 1$.
• Biggest no = 9, there are three quadruples, namely $9, 6, 2, 1$ and $9, 5, 3, 1$ and $9, 4, 3, 2$.
• Biggest no = 8, there are four quadruples, namely $8, 7, 2, 1$ and $8, 6, 3, 1$ and $8, 5, 4, 1$ and $8, 5, 3, 2$.
• Biggest no = 7, there are three quadruples, namely $7, 6, 4, 1$ and $7, 6, 3, 2$ and $7, 5, 4, 2$.
• Biggest no = 6, there is one quadruple, namely $6, 5, 4, 3$.

In total there are $1+1+2+3+4+3+1 = 15$ quadruples, each of which can be ordered in $4! = 24$ ways, for a total answer of $$15\cdot 24 = \boxed{360.}$$

Answer 2

The smallest number which can be expressed as the sum of four distinct positive integers is $1 + 2 + 3 + 4 = 10$. We want to obtain a sum of $18$, so we must add $8$ to this sum. The number $8$ has $15$ partitions into at most four parts in the positive integers. They are: \begin{align*} 8 & = 8\\ & = 7 + 1\\ & = 6 + 2\\ & = 5 + 3\\ & = 5 + 2 + 1\\ & = 5 + 1 + 1 + 1\\ & = 4 + 4\\ & = 4 + 3 + 1\\ & = 4 + 2 + 2\\ & = 4 + 2 + 1 + 1\\ & = 3 + 3 + 2\\ & = 3 + 3 + 1 + 1\\ & = 3 + 2 + 2 + 1\\ & = 2 + 2 + 2 + 2 \end{align*} To construct an ordered-quadruple $(a, b, c, d)$ with $a \leq b \leq c \leq d$ which has sum $18$, add partitions of $8$ into at most four parts to $(1, 2, 3, 4)$ by adding the smallest part to $1$, second smallest part to $2$, third smallest part to $3$, and largest part to $4$. For instance, given the partition $5 + 2 + 1 = 5 + 2 + 1 + 0$ of $8$, we obtain $(1, 2, 3, 4) + (0, 1, 2, 5) = (1, 3, 5, 9)$, which is a strictly increasing quadruple of positive integers with sum $18$.

Hence, there are $15$ strictly increasing quadruples of positive integers with sum $18$. Since each such quadruple may be permuted in $4!$ ways, the number of ordered quadruples of distinct positive integers with sum $18$ is $15 \cdot 4! = 360$.

Answer 3

Note: 1+3+5+9 and 5+1+3+9 are counted as different ways

Well, let's just ignore that. If $a+b+c+d = 18$ there are $4!$ ways to rearrange the terms of $a,b,c,d$ to get $24$ equations $a+b+c+d, a+b+d+c$ etc.

So just count them as though $1+3+5+9$ and $5+1+3+9$ were the same and multiply by $24$.

.....

And stars and bars are the famous way to figure out how many ways to do $a + b + c +d = 16$ where $a < b < c< d$.

Bear with me: $a + b + c + d = 18$ where $0 < a < b < c < d$ if and only if $(a-1) + (b-2)+(c-3)+(d-4) = 8$ where $0 \le a-1 \le b-2\le c-3 \le d-4$ iff $a' + b'+c'+d' =6$ and $a\le b \le c \le d$.

This is "stars and bars". Lay out $a' + b' + c' +d' = 8$ "bars" on the table before you. Then lay out $3$ "stars" between the bars so that you have $a'$ bars, a star, then $b'$ bars, a star, then $c'$ bars, a star, and then $d'$ bars. That way every sum $a'+b'+c'+d' =8$ is represented by some arrangement of $8$ bars and $3$ stars.

How many ways are there to lay out $8$ bars and $3$ stars. Well, you have $8+3 =11$ spaces and you can place the three stars anywhere. The rest of the spaces will be bars.

There are ${11\choose 3} = \frac {9*10*11}{1*2*3} =165$ ways.

So they are $165*24=3960$ ways to make these sums.

....

Note: Ther are $24$ ways to do $1+3+5+9$ and $5+1+3+9$ and $3+9+1+5$ etc. $1+3 +5 +9= 18$ coresponds to $0 + 1+2+5=8$ which corresponds precisely to the patter of stars and bars $*|*||*|||||$.

There are $165$ so patterns and so thare are $165$ equations and $24$ ways to arrange the four terms in the equations.