Combinatorial proof of $\binom{3n}{3} =3\binom{n}{3} +6n\binom{n}{2} +n^3$? 
Give a combinatorial proof of the following identity: $$\binom{3n}{3} =3\binom{n}{3} +6n\binom{n}{2} +n^3.$$

I've been working on this proof for hours, however I'm not able to show LHS = RHS-
I completely understand binomial theorem and few combinatorial proofs but not able to succeed this one.
Help would be appreciated.
 A: Arrange $3n$ balls into 3 rows and each row contains $n$ balls. 
There are $\binom{3n}{3}$ ways to select $3$ balls from them. We can group the seletions into $3$ categories:


*

*Select one ball from each row. There are $n$ choices for each row, this contributes $n^3$ ways of pick the balls.

*Select two balls from one row and one ball from another row. There are $3 \times 2 = 6$ ways to select the rows. Since there are $\binom{n}{2}$ ways to select two balls from a row and $n$ ways to select one ball from a row, this contributes $6 \binom{n}{2} n$ ways to pick the balls.

*Select three balls from a single row. There are $3$ ways to select the row and $\binom{n}{3}$ ways to select three balls from that particular row. This contributes $3\binom{n}{3}$ ways.
These $3$ categories doesn't overlap and exhaust all possible ways to select three balls. As a result,
$$\binom{3n}{3} = n^3 + 6\binom{n}{2} n + 3\binom{n}{3}$$
A: $${3n\choose3}=3{n\choose3}+6n{n\choose2}+n^3$$$$\frac12n\cdot(3n-1)\cdot(3n-2)=\frac12n\cdot(n-1)\cdot(n-2)+3n^2\cdot(n-1)+n^3$$Can you take it from here?
A: $2!=2, 3!=6$, so:
$$\binom{3n}{3}=\frac n2(3n-1)(3n-2)$$
$$3\binom{n}{3}=\frac n2(n-1)(n-2)$$
$$6n\binom{n}{2}=3n^2(n-1)$$
I used that $$\frac{x!}{(x-a)!}=x^{\underline{x-a}}=\prod_{n=0}^{a-1}{(x-n)}$$
See falling factorials
A: Let $A,B,C$ be the $3$ groups of $n$ students each with grades (marks) $A,B,C$, respectively. You need to select $3$ students.
The LHS is simply the combination of $3n$ students chosen $3$ at a time. 
The RHS is to choose $3,2,1$ or $0$ students from $A,B$ and $C$, respectively:
$${n\choose 3}{n\choose 0}{n\choose 0}+{n\choose 2}{n\choose 1}{n\choose 0}+{n\choose 2}{n\choose 0}{n\choose 1}+{n\choose 1}{n\choose 2}{n\choose 0}+{n\choose 1}{n\choose 1}{n\choose 1}+\\
{n\choose 1}{n\choose 0}{n\choose 2}+{n\choose 0}{n\choose 3}{n\choose 0}+{n\choose 0}{n\choose 2}{n\choose 1}+{n\choose 0}{n\choose 1}{n\choose 2}+{n\choose 0}{n\choose 0}{n\choose 3}=\\
{n\choose 3}\cdot 1\cdot 1+{n\choose 2}\cdot n\cdot 1+{n\choose 2}\cdot 1\cdot n+n\cdot {n\choose 2}\cdot 1+n\cdot n\cdot n+\\
n\cdot 1\cdot{n\choose 2}+1\cdot{n\choose 3}\cdot1+1\cdot{n\choose 2}\cdot n+1\cdot n\cdot{n\choose 2}+1\cdot 1\cdot {n\choose 3}=\\
3{n\choose 3}+6n{n\choose 2}+n^3.$$
A: Brute force:
$27n^{3} - 27n^{2}+ 6n = 27n^{3} - 27n^{2} + 6n$
$27n^{3} - 9n^{2} - 18n^{2} + 6n = 3n^{3} - 3n^{2} - 6n^{2} + 6n + 18n^{3} - 18n^{2} + 6n^{3}$
$(9n^{2} - 3n)(3n - 2) = (3n^{2} - 3n)(n - 2)  + 18n^{2}(n-1) + 6n^{3}$
$3n(3n - 1)(3n - 2) = 3n(n - 1)(n - 2)  + 3(6n)n(n-1) + 6n^{3}$
$3n(3n - 1)(3n - 2)/6 = 3n(n - 1)(n - 2)/6  + (6n)n(n-1)/2 + n^{3}$
$\binom{3n}{3} =3\binom{n}{3} +6n\binom{n}{2} +n^3$
A: Notice that the LHS is:
$$\frac{3n \times (3n-1) \times (3n-2)}{3!} = \frac{n \times (3n-1) \times (3n-2)}{2}$$
$$\to \frac{9n^3-9n^2+2n}{2}$$
For the RHS:
$$3 \times \frac{n\times(n-1)\times(n-2)}{3!} + 6n \times \frac{n\times(n-1)}{2!} + \frac{2n^3}{2}$$
$$\Longrightarrow  \frac{n\times(n-1)\times(n-2)}{2} + \frac{6n^2 \times(n-1)}{2} + \frac{2n^3}{2}$$
$$\to \frac{9n^3-9n^2+2n}{2}$$
Hence, RHS=LHS.
