The number of ways to represent a natural number as the sum of three different natural numbers Prove that the number of ways to represent a natural number $n$ as the sum of three different natural numbers is equal to $$\left[\frac{n^2-6n+12}{12}\right].$$
It was in our meeting a year ago, but I forgot, how I proved it.
Let the needed number be $a_n$, where $n\geq6$ and let $b_n$ be number of ways to represent a natural number $n$ as the sum of two different natural numbers.
Thus, $a_n=b_{n-3}+b_{n-6}+...$ because we can go from $(a,b)$, where $a<b$, to $(1,a+1,b+1)$, $(2,a+2,b+2)$...
Thank you for your help!
 A: If $n=r+s+t$ is a representation of a positive integer as a sum of integers which $r>s>t>0$, then
$n-6=(r-3)+(s-2)+(t-1)$ is a representation of $n-6$ as a sum of integers $(r-3)
\ge(s-2)\ge(t-1)\ge0$, that is a partition of $n-6$ into at most three parts.
Therefore $a_n=c_{n-6}$ where $c_n$ is the number of partitions of $n$ into at most three
parts.
By conjugation of partitions, $c_n$ is the number of partitions of $n$ into parts
of size at most $3$. So the generating function of the $c_n$ is
$$C(x)=\sum_{n=0}^\infty c_nx^n=\frac1{(1-x)(1-x^2)(1-x^3)}.$$
Now use the normal manoeuvres with rational functions to find the $n$-th term:
write in partial fractions
$$C(x)=\frac{A}{1-x}+\frac{B}{(1-x)^2}+\frac{C}{(1-x)^3}+
\frac{D}{1+x}+\frac{E+Fx}{1+x+x^2}$$
and go from there.
A: While I agree that generating functions is how I'd approach it now, the slightly more basic approach from back in the day using just high school techniques, will be simply to count it and account for the double counting using Principle of Inclusion and Exclusion.
Without restriction of equality, and without ordering the integers, there are ${ n- 1 \choose 2 } = \frac{ n^2 - 3n + 2 } { 2 }$ ways. If all of the ways are distinct, that we'd double-count them $3!=6$ times due to the order. This naively leads to $ \frac{ n^2 - 3n + 2 } { 12 } $ which is close to the answer, so we're reasonably on the right track.
How many of these ways have 2 values the same? They will be of the form $ \{a, a, b \}$ with $ 1 \leq a \leq \lfloor \frac{n-1}{2} \rfloor$, so there are $ 3\lfloor \frac{ n-1 } { 2 } \rfloor $ of them.
How many of these ways have 3 values the same? They will be of the form $ \{ a, a, a \}$, so there is 1 if $n$ is a multiple of 3. Let $n_3$ be the indicator variable that $ 3 \mid n$. (See notes for how to write this as floor/ceiling functions.)
So how many ways are distinct?
Clearly we want to subtract off the cases where "2 values are the same".
For "3 values the same", note that it is triple counted in "2-values the same", so we have to add $ 2n_3$ in order for this to just be subtracted once.
That will be
$$ \frac{ n^2 - 3n + 2 } { 2}  - 3\lfloor \frac{ n-1 } { 2 } \rfloor +2 n_3.$$
Accounting for the order, we then have to divide by 6, to get
$$ \frac{ n^2 - 3n + 2 } { 12}  -  \frac{1}{2} \lfloor \frac{ n-1 } { 2 } \rfloor + \frac{1}{3} n_3.$$
It remains to check the various cases of $ n \pmod{6}$ that this value is indeed equal to
$$ \lceil \frac{ n^2 - 6n + 12 } { 12 } \rceil $$
Notes:

*

*$n_3 = 1 - \lceil \frac{n}{3} \rceil + \lfloor \frac{n}{3} \rfloor $, if we wanted to stick to floor/ceiling functions.

*Naively $ \frac{ n^2 - 3n + 2 } { 12}  -  \frac{1}{2} ( \frac{ n-1 } { 2 } ) = \frac{ n^2 - 6n + 5}{12}$, which tells us we're very close. We just need to add a (positive) "error term" to account for the other values.

*To verify an identity involving floor/ceiling functions and divisibility indicator variables, checking $ \pmod{k}$ is often the fastest/easiest way. Of course, it's slightly harder to guess what an expression can be simplified into.

*The fanciful name of this approach is Polya enumeration theorem, arising from Group Theory, but the high school student doesn't need to know that.

