Vandermonde Identity

For constants n, m, and r such that 0 <= r <= n + m, the following is true:
(n + m) choose r = Sum ( i = 0..r ) { ( n choose i ) * ( m choose ( r - i )) }
Combinatorically, we can think of this as a problem with a group of people which consists of n lefties and m righties, and we are trying to figure out how many combinations exist such that there are exactly r color blind people in the group. We can categorize each possible arrangement into one of r + 1 categories. The r + 1 categories are indexed from 0 to r, and an arrangement falls under category i if there are exactly i many left-handed color blind people, and the remaining color blind people (r - i) are right-handed. The (n choose i) * (m choose (r - i )) part merely counts how many arrangements fall under category i. The sum adds up all possible arrangements which all fall under one of the categories.

This problem can be visualised:
|              | <-- N
|           ...|.
|          :   |:
|          :   |:
'--------------':<-- R
|          :...|:
|              |
|              | <-- M
    fig. 1

The size/cardinality of sets N, R, M are fixed, and R is a subset of the disjoint union of N and M. As you can see, more of R can be under M, or more could be under N, and the identity's summation is used to consider all such possibilities.

See also: