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: