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

• @MagedSaeed yes – m.saza Nov 4 '18 at 4:23
• The answer you picked does not address your question (combinatorial proof, meaning minimal algebra). Of course, if you were not actually asking for a combinatorial proof, you should edit your question to just ask for a proof. =) – user21820 Nov 4 '18 at 6:22
• Also, unrelated to my above comment, please read the how-to-ask page. – user21820 Nov 4 '18 at 6:23

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

• Great answer +1! – Don Thousand Nov 4 '18 at 3:42

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

• Why do people post algebraic solutions when the OP is asking specifically (in boldface) for a combinatorial proof? Not gonna vote down algebraic solutions though. Just saying. And +1 only to Achille Hui. – Ken Draco Nov 4 '18 at 3:59
• @KenDraco I might have misread the question at first. Oops! – Don Thousand Nov 4 '18 at 4:00
• I got it. I myself am prone to such things. I just mean all the answers below -:) – Ken Draco Nov 4 '18 at 4:09
• I feel dirty since I don't feel like this should be the accepted answer. – Don Thousand Nov 4 '18 at 4:25
• Don't. If you take a look at the mess and trolling/incompetency (I'm shocked) on other SE sites (including astronomy), than math and physics are a true paradise. – Ken Draco Nov 4 '18 at 4:33

$$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)}$$

• This would be an algebraic proof, not a combinatorial proof. – Mark S. Nov 4 '18 at 3:37

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

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 proof that thinks about combination (as in choosing n objects from m objects) is better because it trains intuition. But for simple problems, algebra and brute force is sufficient. – R zu Nov 4 '18 at 3:30
• This would be an algebraic proof, not a combinatorial proof. – Mark S. Nov 4 '18 at 3:38

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.

• This is an algebraic proof, not a combinatorial one. See the answer of Achille Hui for a combinatorial proof. – N. F. Taussig Nov 4 '18 at 16:06
• You may notice that the OP was puzzling how the RHS is equal to the LHS. – Maged Saeed Nov 5 '18 at 3:23