# How many solutions are there for $3$ natural numbers adding to $24$?

I attempted stars and bars and got $$\binom{26}{2}$$ but that is saying $$1 + 1 + 22$$ and $$22 + 1 + 1$$ are both distinct, which should not be the case.

• "which should not be the case" Why wouldn't it be the case that those are distinct? Walking east $22$ yards and then north $1$ yard gets you to a different place than walking east $1$ yard and then north $22$ yards doesn't it? Dec 21, 2022 at 1:56
• If you insist on order not mattering, then what you are looking for are the restricted partitions of $24$ into $3$ (presumably nonempty) parts. Its not going to have a nice simple formula like the stars-and-bars case. Dec 21, 2022 at 1:58

There is one solution with $$x_1=x_2=x_3.$$ For each even number $$n$$ from $$0$$ to $$24$$ except for $$8$$, there is one solution with $$x_1=n$$ and $$x_2=x_3 \neq n$$, for a total of $$12$$ such solutions. If order matters, we multiply by $$3$$, yielding $$36$$ solutions.

That means that of the $$\binom{26}{2}$$ solutions (in which order matters), there are $$37$$ solutions that don't use three different numbers as $$x_1, x_2, x_3$$. That means there are $$\binom{26}{2}-37=325-37=288$$ solutions using $$3$$ different numbers in which order matters. Dividing by $$6$$, we get $$48$$ solutions with three distinct numbers in which order doesn't matter.

So I conclude there are $$48+12+1=61$$ distinct solutions (ignoring order).

There's a nice combinatorial argument due to Frame (American Mathematical Monthly 46 (1940) p.664) about counting triangles inscribed in a circle that leads to the surprising formula $$p(n,3) = \left\{\frac{n^2}{12}\right\},$$ i.e., the number of 3 part partitions of $$n$$ is the nearest integer to $$n^2/12$$. If by natural numbers you mean positive parts, then your answer is 48 by this formula. If instead you mean to allow 0 as one or two of the three parts, then the easier formulas $$p(n,2) = \left\lfloor \frac{n}{2} \right\rfloor$$ (integer floor) and $$p(n,1) = 1$$ give the $$p(24,3) + p(24,2) + p(24,1) = 48 + 12 + 1 = 61$$ count of the other answers.

It sounds like you want to find integer solutions to $$x_1+x_2+x_3 = 24 \\ 0 \le x_1 \le x_2 \le x_3$$ Perform a change of variables $$y_1=x_1$$, $$y_2=x_2-x_1$$, $$y_3=x_3-x_2$$, yielding $$3y_1+2y_2+y_3 = 24 \\ y_i \ge 0$$ You can count the solutions recursively by conditioning on the value of $$y_i$$.

Another approach to count the solutions $$(y_1,y_2,y_3)$$ is to use a generating function. Explicitly, you want the coefficient of $$z^{24}$$ in $$(1+z^3+z^6+\dots)(1+z^2+z^4+\dots)(1+z+z^2+\dots) =\frac{1}{(1-z^3)(1-z^2)(1-z)}.$$

The number of solutions turns out to be $$61$$.

I found the exact formula for $$p_n(k)$$, the number of partitions of $$n$$ into at most $$k$$ parts, here:

$$p_3(n)=[\frac{n^2}{12}+\frac{n}{2}+\frac{47}{12}]+[-\frac{1}{8},\frac{1}{8}]+[-\frac{1}{9}, -\frac{1}{9},\frac{2}{9}].$$

Now, $$24\equiv 2\pmod 2$$ and $$24\equiv 3\pmod 3$$. Now, according to the article, I think, we choose the last fractions in the formula: $$p_3(24)=[\frac{n^2}{12}+\frac{n}{2}+\frac{47}{72}+\frac{1}{8}+\frac{2}{9}](24)=\frac{12^2}{12}+\frac{12}{2}+\frac{47}{72}+\frac{1}{8}+\frac{2}{9}=61.$$

We can olso compute this number by means of a recursive formula. Let $$p(n,k)$$ be the number of partitions of $$n$$ into exactly $$k$$ parts. Then we have the recursion: $$p(n,k)=p(n-1,k-1)+p(n-k,k).$$ Hence, also by using $$p(n,2)=\lfloor\frac{n}{2}\rfloor$$,

$$\begin{array} .p_3(24)&=p(24,1)+p(24,2)+p(24,3)\\ &=1+\lfloor\frac{24}{2}\rfloor+p(23,2)+p(21,3)\\ &=1+12+\lfloor\frac{23}{2}\rfloor+p(20,2)+p(18,3)\\ &=13+11+\lfloor\frac{20}{2}\rfloor+p(17,2)+p(15,3)\\ &=24+10+\lfloor\frac{17}{2}\rfloor+p(14,2)+p(12,3)\\ &=34+8+\lfloor\frac{14}{2}\rfloor+p(11,2)+p(9,3)\\ &=42+7+\lfloor\frac{11}{2}\rfloor+p(8,2)+p(6,3)\\ &=49+5+\lfloor\frac{8}{2}\rfloor+p(5,2)+p(3,3)\\ &=54+4+2+1\\ &=61. \end{array}$$