1

How many ways are there to express a natural number, $n$, as the sum of three whole numbers, $a,b,c$, where $a,b,c$ are allowed to be 0 but are unique? For example: $n=9$ there are only seven ways: $1+2+6, 1+3+5, 2+3+4, 0+1+8, 0+2+7, 0+3+6, 0+4+5$.

PS: Looking at some previous [answers]Generating function for counting compositions of $n$, I learnt this "thing" is known as partitions of $n$. But I did not find an answer that includes 0 and does not allow repetitions. Number theory is not my area, and all I would like to know is if some analytical formula can determine this.

Bill Dubuque
  • 272,048
bissi
  • 64
  • 11

2 Answers2

1

Suppose $S$ is the set of ordered triplets $\{x,y,z\}$ such that $x+y+z=n$. As you know the size of $S$ is $n+2 \choose 2$. There are three types of triplets in $S$.

  1. $x,y,z$ are all distinct.
  2. Exactly two of $x,y,z$ are the same.
  3. $x=y=z$.

Let $t_1,t_2,t_3$ be the number of triplets of type 1, 2 and 3 respectively. So, $t_1+t_2+t_3=|S|$. $t_3=1$ if $n$ is divisible by 3 otherwise $t_3$ = 0. The number of pairs $\{u,v\}$ such that $2u+v=n$ is $ \lfloor{\frac{n}{2}} \rfloor - t_3 + 1 $. Each such pair contributes exactly 3 ordered triplets $\{u,u,v\},\{u,v,u\},\{v,u,u\}$ in $S$. Hence, $t_2= 3(\lfloor{\frac{n}{2}} \rfloor - t_3 + 1)$. You are looking for the number of unordered triplets $\{a,b,c\}$ such that $a+b+c=n$. This count is exactly equal to $t_1/6$ as each such unordered triplet $\{a,b,c\}$ contributes 6 ordered triplets of type 1 in $S$. So, the count is $$\frac{|S|-t_2-t_3}{6} = \frac{\binom{n+2}{2}-3(\lfloor{\frac{n}{2}} \rfloor - t_3 + 1)-t_3}{6}= \frac{\binom{n+2}{2}-3(\lfloor{\frac{n}{2}} \rfloor + 1)+2t_3}{6}.$$ Taking your example of $n=9$, it is $$\frac{\binom{9+2}{2} -3(\lfloor{\frac{9}{2}} \rfloor + 1)+2}{6} = \frac{55-3\cdot5+2}{6}=7.$$

RobPratt
  • 45,619
Amritanshu singh
  • 61
  • 5
0

A simple formula for partitions also answers your question. There's a result that goes back to at least De Morgan 1843 that the number of three (positive) part partitions of $n$ is $$ \left\{ \frac{n^2}{12} \right\},$$ the integer nearest to $n^2/12$. Frame gave a nice combinatorial proof of this in a 1940 American Mathematical Monthly problem (v47 #9 p664); it's an exercise in van Lint and Wilson's combinatorics textbook.

For instance, there are $\{ 9^2 / 12 \} = 7$ three part partitions of 9, $$ 7+1+1, \quad 6+2+1, \quad 5+3+1, \quad 5+2+2, \quad 4+4+1, \quad 4+3+2, \quad 3+3+3. $$ To get the three term sums you want (distinct parts, zero allowed), add 1 to the largest part and subtract 1 from the smallest part of each partition, e.g., $$ 8+1+0, \quad 7+2+0, \quad 6+3+0, \quad 6+2+1, \quad 5+4+0, \quad 5+3+1, \quad 4+3+2,$$ your list. This transition guarantees that the resulting parts are distinct, allows for 0 when the smallest part of the original partition is 1, and does not change the sum.

Brian Hopkins
  • 2,257