7
$\begingroup$

Prove that $${^{404}\mathrm C_4}-{^4\mathrm C_1}\cdot{^{303}\mathrm C_4}+{^4\mathrm C_2}\cdot{^{202}\mathrm C_4}-{^4\mathrm C_3}\cdot{^{101}\mathrm C_4} =(101)^4$$

I tried writing $101=102-1$, but couldn't move forward.

$\endgroup$
7
$\begingroup$

The question is equivalent to:

You have $4$ groups with $101$ items in each group.

What is the number of ways for selecting $4$ items, where each item is from a different group?


The given solution uses inclusion/exclusion principle:

  • Include the number of ways for selecting $4$ items from up to $\color\red4$ groups: $\binom{4}{\color\red4}\cdot\binom{101\cdot\color\red4}{4}$
  • Exclude the number of ways for selecting $4$ items from up to $\color\red3$ groups: $\binom{4}{\color\red3}\cdot\binom{101\cdot\color\red3}{4}$
  • Include the number of ways for selecting $4$ items from up to $\color\red2$ groups: $\binom{4}{\color\red2}\cdot\binom{101\cdot\color\red2}{4}$
  • Exclude the number of ways for selecting $4$ items from up to $\color\red1$ groups: $\binom{4}{\color\red1}\cdot\binom{101\cdot\color\red1}{4}$

Of course, a simpler solution would be to simply choose one item from each group: $101^4$.

$\endgroup$
  • $\begingroup$ You should say "What is the number of ways of selecting four items, where no two of them are from the same group?" $\endgroup$ – N. F. Taussig Mar 27 '16 at 11:13
  • $\begingroup$ @N.F.Taussig: You're right, I was actually wondering with myself what exact terminology to use there... Thanks :) $\endgroup$ – barak manos Mar 27 '16 at 11:14
6
$\begingroup$

The given expression here is the coefficient of $x^4$ in $P(x) := ((1+x)^{101}-1)^4$. You can see this by first expanding $(y-1)^4$, then putting $y = (1+x)^{101}$ and expanding it in terms of $x$.

But $P(x) =((1+101x+...)-1)^4 = (101x+...)^4 = 101^4\cdot x^4(1+...)^4$ where the dots represent higher powers of $x$.

Thus, the coefficient of $x^4$ in $P(x)$ is indeed $101^4$.

$\endgroup$

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.