8
$\begingroup$

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.

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

6 Answers 6

21
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Great answer +1! $\endgroup$ Nov 4, 2018 at 3:42
2
$\begingroup$

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

$\endgroup$
5
  • 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, 2018 at 3:59
  • 2
    $\begingroup$ @KenDraco I might have misread the question at first. Oops! $\endgroup$ Nov 4, 2018 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, 2018 at 4:09
  • $\begingroup$ I feel dirty since I don't feel like this should be the accepted answer. $\endgroup$ Nov 4, 2018 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, 2018 at 4:33
1
$\begingroup$

$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

$\endgroup$
1
  • 5
    $\begingroup$ This would be an algebraic proof, not a combinatorial proof. $\endgroup$
    – Mark S.
    Nov 4, 2018 at 3:37
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
2
  • 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, 2018 at 3:30
  • 6
    $\begingroup$ This would be an algebraic proof, not a combinatorial proof. $\endgroup$
    – Mark S.
    Nov 4, 2018 at 3:38
0
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .