Find the number of integer triplets such that $x+y+z=n$ and $x\geq y\geq z > 0$
Let $n$ be an integer such that $n > 3$ and let $S$ be the set of all ordered triples of strictly positive integers $(x, y, z)$ whose sum is $n$. Show that $S$ has $\frac{1}{2} (n − 1) (n − 2)$ elements.
Distinguishing cases, find the number of integer triples $(x, y, z)$ such that$x + y + z = n$ and $x \geq y \geq z > 0$
I’ve managed to prove the first part, that $S$ has $\frac{1}{2}(n-1)(n-2)$ elements but I am struggling with the latter part.
$\endgroup$ 72 Answers
$\begingroup$Hints for the second one:
Find the number of integer triples $(x, y, z)$ such that$x + y + z = n$ and $x \geq y \geq z > 0$
let $y = z+k_1$ and $x = y+k_2.$ with $k_1, k_2 \geq 0.$ Then we have $3z +2k_1 +k_2 =n.$ Then let $z_1 = z-1$ then $z_1 \geq 0.$ Finally we have $3z_1 + 2k_1+k_2 = n- 3.$ Note that $z_1, k_1, k_2 \geq 0.$
There are standard tricks to solve such an equation. Either you can use the General Principle of Inclusions & Exclusions or the idea of generating functions.
Basically, Shubham Johri gave you the solution before I wrote these hints.
$\endgroup$ $\begingroup$Here is an easy method that uses your answer to the first part and doesn't reinvent the wheel. Suppose the set containing triples satisfying the second part is denoted by $T\subseteq S$. In $S$ there are triples where:
All $x,y,z$ are distinct. Suppose there are $m$ such triples in $S$. Such triples permute in $3!=6$ ways, i.e. the unordered triple $(x,y,z)$ makes $6$ appearances in $S$. When $x,y,z$ are ordered in non-increasing order as per the requirement in the second part of the question, we get one unique ordering corresponding to the $6$ appearances. Thus we have $m/6$ triples in $T$ where all coordinates are distinct.
Two coordinates are identical. Suppose the identical coordinates have value $1$, then the third coordinate has value $n-2$. Corresponding to this selection of values, we have $3!/2!=3$ triples in $S$. Similarly, when $2$ is repeated, the third coordinate is $n-4$ and this selection is repeated $3$ times. The identical coordinates can at most be $\lfloor(n-1)/2\rfloor$ as the third coordinate needs to be at least $1$. Thus the total number of triples in $S$ where two coordinates are identical is $3\lfloor(n-1)/2\rfloor$. Corresponding to these we have $\lfloor(n-1)/2\rfloor$ triples in $T$.
Note that in the second case we would have encountered a triple where all three coordinates are identical had $3\mid n$. This particular triple would not have $3$, but only $1$ occurrence in $S$. Thus when $3\nmid n$, we have $$m+3\lfloor(n-1)/2\rfloor=\frac12(n-1)(n-2)\\|T|=m/6+\lfloor(n-1)/2\rfloor$$
And when $3\mid n$, we subtracted $2$ from the $3$ occurrences of the triple $(n/3,n/3,n/3)$ we counted in case $2$ to get$$m+3\lfloor(n-1)/2\rfloor=\frac12(n-1)(n-2)+2\\|T|=m/6+\lfloor(n-1)/2\rfloor$$
All in all$$|T|=\frac1{12}(n-1)(n-2)+\frac12\lfloor(n-1)/2\rfloor+\begin{cases}1/3,&3\mid n\\0,&3\nmid n\end{cases}$$
I hope I have not made any errors.
$\endgroup$
