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$.
Number of $j$ element subsets of $\{x_1,x_2,\ldots,x_n,y_1,y_2,\ldots,y_m\}$
2
$\begingroup$
combinatorics
2 Answers
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.