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

Question

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.

Answer 1

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).

Answer 2

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.

Answer 3

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$.

Answer 4

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}$$