Number of distinct triplets with given sum

Question

I just came across a problem that I couldn't find a proper formula.

I have to find number of distinct triples that can be made from positive numbers less than N and sum of triplet must be N.

Also, numbers should not repeat in the triplets.

Answer 1

Since $1 + 2 + 3 = 6$, for $N < 6$, there are no solutions. Therefore, from here on, we will assume $N \geq 6$.

The number of triples of positive integers that satisfy the equation $$x_1 + x_2 + x_3 = N$$ is equal to the number of ways two addition signs can be placed in the $N - 1$ spaces in a row of $N$ ones, which is $$\binom{N - 1}{2}$$ From these, we must exclude those solutions in which two or more of the numbers in the triple are equal. We consider cases.

Case 1: $N$ is not divisible by $3$.

In this case, not all three numbers can be equal. Since the three numbers in the triples must be positive, the number of ways two of the three numbers can be equal is $$\left\lfloor \frac{N - 1}{2} \right\rfloor$$ where $\lfloor x \rfloor$ denotes the greatest integer that is less than or equal to $x$, since each pair of repeated numbers sums to an even number less than $N$ and there are $\frac{N - 1}{2}$ even numbers less than $N$. Since there are three ways to place the third number, the number of ordered triples with sum $N$ in which no two of the numbers are equal is $$\binom{N - 1}{2} - 3\left\lfloor \frac{N - 1}{2} \right\rfloor$$

Case 2: $N$ is divisible by $3$.

We must modify the above argument to account for the triple $\left(\frac{N}{3}, \frac{N}{3}, \frac{N}{3}\right)$. When we subtract those triples in which two of the numbers are the same, we remove this triple three times, once for each place the third number in the triple can be placed. Since we only wish to remove it once, we must add $2$ to the total we found above, which yields $$\binom{N - 1}{2} - 3\left\lfloor \frac{N - 1}{2} \right\rfloor + 2$$

Answer 2

This problem is called stars and bars. Here's a summary of the content of that link. Start with $N$ dots in a line (here $N = 7$).

o o o o o o o

Observe that splitting this line into three (nonempty) parts means finding a triple of (positive) numbers whose sum is $N$.

So we just need to count ways to do that. Let's divide the dots by placing bars between them. For example,

o o | o o o o | o

would correspond to the triple $(2, 3, 1)$.

There are $N - 1$ spots to place bars, and we have to place $2$ of them to make a triple. So there are $\binom{N - 1}{2}$ such triples.