?

Combinatorics

Free Version

Upgrade subject to access all content

Moderate

Pair the Binomial Identity with its Combinatorial Proof

COMBIN-VIGIJT

The following text suggests a double counting (or counting in two ways) argument which can be interpreted to give a proof of a combinatorial identity.

Pi day is coming up and we are selling t-shirts for math club to fundraise for our pi day event. The shirts we are selling come in small, medium, and large sizes. In each of the sizes, we have $n$ different colors for customers to choose from.

My history teacher says she will buy three shirts but only asked that we do not get two shirts of the same color and size. So she doesn't want two purple small shirts but a purple small and a purple medium is okay. There are many ways I could pick these three shirts.

In particular, I could pick three shirts, all the same size, making sure not to pick two of the same color. On the other hand, I could pick two of one size and then one more from either of the two remaining sizes. The only other option I have is to pick exactly one of each size.

Which combinatorial identity corresponds to the proof idea given above?

A

$\binom{n}{3}=\binom{\frac{n}{3}}{3}+\binom{\frac{n}{3}}{2}\frac{n}{3}+\binom{\frac{n}{3}}{3}$

B

$\binom{3n}{3}=3\binom{n}{3}+2n\binom{n}{2}+\binom{n}{1}^3$

C

$\binom{3n}{3}=3\binom{n}{3}+6n\binom{n}{2}+\binom{n}{1}^3$

D

$\binom{3n}{3}=3n^3+3(2n)n^2+n^3$