Combinatorial proof of $\binom{3n}{3} =3\binom{n}{3} +6n\binom{n}{2} +n^3$?

Question

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.

Answer 1

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:

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

2. 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.

3. 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}$$

Answer 2

$${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?

Answer 3

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$

Answer 4

$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

Answer 5

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.

Answer 6

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.$$