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.
Best Answer
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}$$