How elements in Vandermonde’s formula be well-defined?

50 Views Asked by At

Vandermonde’s formula:

For any non-negative integers: $m, n, k$ $${m+n \choose k}=\sum_{j=0}^k{m \choose j}{n \choose k-j}$$

For ${x \choose y}$ to be defined, $x\geq y$. But in Vandermonde’s formula, there are possibly cases where $j=m+1>m$ or $k-j=n+1>n$. So how can ${m \choose j}={m \choose m+1}$ and ${n \choose k-j}={n \choose n+1}$ be defined?

1

There are 1 best solutions below

3
On BEST ANSWER

Logically speaking, $\binom mn$ is the number of ways of choosing $n$ objects out of $m$, or the number of subsets of size $n$, of a subset of size $m$. There are no subsets of size $n$ if $n > m$, so $\binom mn$ should be defined as $0$ in this case.


Furthermore, when we look at a proof of Vandermonde's identity via sets, this makes even more sense :

$\binom{m+n}k$ is the number of subsets of size $k$ of a set with size $m+n$. Let us call the big set as $A$.

Alternatively, partition $A = B \ \cup \ C$, where $|B| = m,|C| = n$ and the union is therefore disjoint. The choice of $B$ and $C$ does not matter.

Now, for any subset $K \subset A$, $K = K \cap A = (K \cap B) \cup (K \cap C)$, where the union is disjoint.

Therefore, any such $K$ is formed by taking a subset of $B$ and a subset of $C$ whose sum of cardinalities is $|K|$.

Consequently, the answer is given as follows : for each $j = 0 \to k$, any subset of $B$ of size $j$ can be combined with any subset of $B$ of size $k-j$, and the number of ways of doing this is $\binom mj \binom n{k-j}$(even if $\mathbf{k -j> n}$ or $\mathbf{m > j}$), which then gets summed to give the answer.

Hence, the interpretation of $\binom mn = 0$ if $n > m$ works out with this logic.