How many combinations of $3$ natural numbers are there that add up to $30$?

Question

How many combinations of $3$ natural numbers are there that add up to $30$?

The answer is $75$ but I need the approach.

Although I know that we can use $_{(n-1)}C_{(r-1)}$ i.e. $_{29}C_2 = 406$ but this is when $a, b, c$ are distinguishable which is not the case here.

Please explain.

EDIT three such examples:
$\begin{align} 1+1+28 \\ 10+10+10 \\ 1+2+27 \\ ... \end{align}$

Answer 1

The ideas of this method is known as burnsides lemma in group theory.

As you pointed out, the number of positive integer solutions to $a+b+c=30$ is ${29 \choose 2}=406$ by the stars and bars. However it over counts the total because the numbers are indistinguishable.

How many times does it over count? If all the numbers are the same, I.e. $a=b=c$, then there is just one way.

If two of the numbers are equal, then $2a+c=30$, and there are 14 ways corresponding to $a=1$ to 14. However we would double count $a=b=c$ so there are 13 ways. Each of these 13 ways would lead to 39 ways if the numbers were indistinguishable.

Now, of the 406 distinguished ways, lets subtract off the $1+39=40$ distinguished ways listed above, giving us 366. These correspond to distinct a, b, c values. Each of these ways are counted 6 times. Hence there are $366/6=61$ undistinguished ways.

Now we add back the 13 undistinguished from the two same one different, and the 1 undistinguished from three same, and we get $61+13+1=75$

Answer 2

If we want the answer to a small problem like this, we can list systematically and count.

We only count the number of partitions of $30$ into $3$ parts. The same idea can be used to produce an explicit formula for the number of partitions of $n$ into $3$ parts. For one notices a simple pattern. If we want $4$ parts, a similar idea works. In principle what we use below is a recurrence, from the easy $2$ parts to the less easy $3$ parts.

We make a list by smallest element in the partition:

Smallest $10$: $1$ way

Smallest $9$: $2$ ways.

Smallest $8$: $4$ ways (next one is $8$ to $11$)

Smallest $7$: $5$ ways

Smallest $6$: $7$ ways (next one $6$ to $12$)

Smallest $5$: $8$ ways

Smallest $4$: $10$ ways.

Smallest $3$: $11$ ways

Smallest $2$: $13$ ways

Smallest $1$: $14$ ways (next one $1$ to $14$)

Note the nice pattern of increase of the numbers. Now add.

Another way: The following is another direct computational approach. Let $f(n)$ be the number of partitions of $n$ into $3$ parts. The smallest part can be (i) greater than $1$ or (ii) equal to $1$.

In Case (i), by removing a $1$ from each part, we get a partition of $n-3$, and we get all partitions of $n-3$ in this way.

To count the Case (ii) possibilities, note that we must partition $n-1$ into two parts. If $n-1$ is odd , this can be done in $(n-2)/2$ ways. If $n-1$ is even it can be done in $(n-1)/2$ ways.

So we have obtained the recurrence $f(n)=f(n-3)+(n-2)/2$ if $n$ is even, and $f(n)=f(n-3)+(n-1)/2$ if $n$ is odd.

Armed with this recurrence, we can to $n=30$ quickly by $3$'s from the base case $n=3$.