1
$\begingroup$

Using an inclusion-exclusion argument prove that

$\sum_{k=0}^{m}(-1)^{k}\binom{m}{k}\binom{n-k}{r} = \binom{n-m}{r-m}$

Assuming $m \leq r \leq n$.

I'm not sure how to begin this, can anyone help me get started?

$\endgroup$
1
$\begingroup$

I’ll get you started by explaining how I attacked it; I’ll leave the finish to you, but feel free to ask questions if you get completely stuck. As usual $[s]$ denotes the set $\{1,\ldots,s\}$.

On the lefthand side the factors $(-1)^k$ and $\binom{m}k$ look like part of the machinery of an inclusion-exclusion calculation, leaving $\binom{n-k}r$ as the meat of the term. It’s the number of $r$-element subsets of a set of $n-k$ elements. On the righthand side we have the number of $(r-m)$-element subsets of something; is there any way to interpret $\binom{n-m}{r-m}$ in terms of $r$-element subsets of something, to make it match the lefthand side better?

Yes: $\binom{n-m}{r-m}$ is the number of $r$-element subsets of $[n]$ that contain $[m]$ as a subset. Thus, we’d like to interpret the lefthand side as an inclusion-exclusion calculation of the number of $r$-element subsets $S$ of $[n]$ such that $[m]\subseteq S$.

Write out the first few terms of the summation:

$$\binom{n}r-\binom{m}1\binom{n-1}r+\binom{m}2\binom{n-2}r-\ldots$$

That first term is just the total number of $r$-element subsets of $[n]$. We want to throw out the ones that don’t contain $[m]$ as a subset. How many of these ‘bad’ $r$-element subsets of $[n]$ are there?

For each $i\in[m]$ let $\mathscr{A}_i$ be the set of $r$-element subsets of $[n]$ that do not contain $i$; then

$$\bigcup_{i\in[m]}\mathscr{A}_i$$

is the set of ‘bad’ $r$-element subsets of $[n]$, and there are therefore

$$\binom{n}r-\left|\bigcup_{i\in[m]}\mathscr{A}_i\right|$$

$r$-subsets of $[n]$ that do contain $[m]$ as a subset. The inclusion-exclusion principle says that

$$\left|\bigcup_{i\in[m]}\mathscr{A}_i\right|=\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|-1}\left|\bigcap_{i\in I}\mathscr{A}_i\right|\;,$$

so there are

$$\binom{n}r-\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|-1}\left|\bigcap_{i\in I}\mathscr{A}_i\right|=\binom{n}r+\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|}\left|\bigcap_{i\in I}\mathscr{A}_i\right|$$ $r$-element subsets of $[n]$ that contain $[m]$ as a subset. To finish the argument, you need to show that

$$\binom{n}r+\sum_{\varnothing\ne I\subseteq[m]}(-1)^{|I|}\left|\bigcap_{i\in I}\mathscr{A}_i\right|=\sum_{k=0}^m(-1)^k\binom{m}k\binom{n-k}r\;.$$

A couple questions that may help:

  • For a given $k$, how many $k$-element subsets of $[m]$ are there?
  • Can you express $\left|\bigcap_{i\in I}\mathscr{A}_i\right|$ in terms of $|I|$?
$\endgroup$
  • $\begingroup$ the downvoter was maybe someone who doesn't like complete detailed answers to short questions (+1 btw) $\endgroup$ – user153330 Mar 20 '16 at 12:05

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.