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.

  • $\begingroup$ @MagedSaeed yes $\endgroup$ – m.saza Nov 4 '18 at 4:23
  • $\begingroup$ 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. =) $\endgroup$ – user21820 Nov 4 '18 at 6:22
  • $\begingroup$ Also, unrelated to my above comment, please read the how-to-ask page. $\endgroup$ – 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}$$

  • $\begingroup$ Great answer +1! $\endgroup$ – 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?

  • 4
    $\begingroup$ 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. $\endgroup$ – Ken Draco Nov 4 '18 at 3:59
  • 2
    $\begingroup$ @KenDraco I might have misread the question at first. Oops! $\endgroup$ – Don Thousand Nov 4 '18 at 4:00
  • $\begingroup$ I got it. I myself am prone to such things. I just mean all the answers below -:) $\endgroup$ – Ken Draco Nov 4 '18 at 4:09
  • $\begingroup$ I feel dirty since I don't feel like this should be the accepted answer. $\endgroup$ – Don Thousand Nov 4 '18 at 4:25
  • $\begingroup$ 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. $\endgroup$ – 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)}$$

See falling factorials

  • 5
    $\begingroup$ This would be an algebraic proof, not a combinatorial proof. $\endgroup$ – 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$

  • 1
    $\begingroup$ 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. $\endgroup$ – R zu Nov 4 '18 at 3:30
  • 6
    $\begingroup$ This would be an algebraic proof, not a combinatorial proof. $\endgroup$ – 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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.