Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3 
Find the Number of ways of selecting 3 numbers from $\{1,2,3,\cdots,3n\}$ such that the sum is divisible by 3. (Numbers are selected without replacement).

I made a list like this:
 
The sum of all elements along such diagonals are divisible by 3. Number of ways of selecting such numbers is $3n-2$
Then I shifted the second row by one element and third row by one element behind second row:

Again the sum of elements are divisible by 3. Total number of ways is $3n-4$.
In the next list, I will shift the second row by two elements and third row by 2 elements behind second row. The elements along a diagonal will be $\{1,4,7\}\cdots\{3n-6,3n-3,3n\}$. Sum is divisible by 3. Number of such possibilities is $3n-6$.
The total number of ways is $3n-2+3n-4+3n-6+\cdots$
what will be the last case?
 A: Let $S = \{1, 2, 3, \ldots, 3n - 2, 3n - 1, 3n\}$.  Let 
\begin{align*}
A & = \{k \in S \mid k \equiv 0 \pmod{3}\}\\
B & = \{k \in S \mid k \equiv 1 \pmod{3}\}\\
C & = \{k \in S \mid k \equiv 2 \pmod{3}\}
\end{align*}
Observe that $|A| = |B| = |C| = n$.  We can choose three numbers from $S$ in the following ways:


*

*Choose $3$ elements of $A$, which can be done in $\binom{n}{3}$ ways.

*Choose $3$ elements of $B$, which can be done in $\binom{n}{3}$ ways.

*Choose $3$ elements of $C$, which can be done in $\binom{n}{3}$ ways.

*Choose $1$ element from each subset, which can be done in $\binom{n}{1}^3$ ways.


Hence, the number of ways of selecting a subset of three numbers in $S$ whose sum is divisible by $3$ is 
\begin{align*}
3\binom{n}{3} + \binom{n}{1}^3 & = 3 \frac{n(n - 1)(n - 2)}{3!} + n^3\\
& = \frac{n^3 - 3n^2 + 2n}{2} + n^3\\
& = \frac{3n^3 - 3n^2 + 2n}{2}
\end{align*}
A: Number of solutions to $a+b+c=k$ where $a,b,c$ are positive integers is $\binom{k-1}{2}$. So the number of ways to choose is
$$
\sum_{k=1}^n\binom{3k-1}{2}={n\over2}(3n^2-1)
$$
Edit: As JMoravitz notes below this counting accounts for ordered triples from the given set rather than subsets.
