2
$\begingroup$

If $S = \{x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_m \}$ Explain why $\sum\limits_{k = 0}^j {n \choose k } {m \choose j-k}$ is the number of $j$-element subsets of $S$.

2 Answers 2

10

To select a $j$-element subset of $S$, we can first decide how many $x$s will be in the set; call this $k$. Then $0\leq k\leq j$. Once we know the subset will have $k$ of the $x$s, then it will have $j-k$ of the $y$s.

How many ways can we select $k$ of the $x_i$, and how many ways can we select $j-k$ of $y$s? What should we do with these two numbers?

And since we can select $k=0$, or $k=1$, or $k=2$, or..., what should we do with these quantities?

5

This is Vandermonde's identity again.