1
$\begingroup$

I would like to obtain a closed form for the following:

$${n \choose 0}{n \choose k} + {n \choose 1}{n-1 \choose k-1} + {n \choose 2}{n-2 \choose k-2} + ... + {n \choose k}{n-k \choose 0}$$

To me, this looked like it closely resembles the Binomial Theorem, which I know to be: $(a+b)^k=\sum_{k=0}^n\binom nk a^k b^{n-k},$ but I couldn't get it to work.

The $\sum{n \choose k}$ bit falls nicely in the Binomial expansion, but I don't know how to manipulate $a$ and $b$ to represent $\sum_{i=0}{n-i \choose k-i}$. How should I go about this?

$\endgroup$
6
$\begingroup$

Your sum can be rewritten in sigma notation as $$ \sum_{j = 0}^k \binom{n}{j} \binom{n-j}{k-j}.$$ We observe that for $j = 0, \dots, k$, we have $$ \binom{n}{j} \binom{n-j}{k-j} = \frac{n!}{j!(n-j)!} \frac{(n-j)!}{(n-k)!(k-j)!} = \frac{n!}{k! (n-k)!} \frac{k!}{j!(k-j)!} = \binom{n}{k} \binom{k}{j}.$$ Summing over $j$ gives $$ \sum_{j = 0}^k \binom{n}{j} \binom{n-j}{k-j} = \sum_{j = 0}^k \binom{n}{k} \binom{k}{j} = 2^k \binom{n}{k}.$$

$\endgroup$
4
$\begingroup$

Think about what each term counts. $\binom{n}{i}$ counts the number of ways to choose $i$ things from $n$ things, and $\binom{n-i}{k-i}$ counts the number of ways to choose $k-i$ things from $n-i$ things. So we could interpret this as the following: start with a group of $n$ objects, then pick $i$ of them to be assigned to "group A" and pick $k-i$ of the remaining $n-i$ objects to be assigned to "group B". The number of ways to do this is $\binom{n}{i}\binom{n-i}{k-i}$.

If we sum these from $i=0$ to $i=k$, then we are counting all the ways that we can choose some number of objects and assign them to "group A" and some number of objects and assign them to "group B" such that the total size of "group A" and "group B" is always $k$. If we want a closed form for this quantity, we should calculate it in another way. So we could first pick the $k$ objects that will be assigned to "group A" or "group B" (there are $\binom{n}{k}$ ways to do this), then for each object, assign it to "group A" or "group B". There are $2^k$ ways to make these assignments. So, $$\sum_{i=0}^k \binom{n}{i}\binom{n-i}{k-i}=\binom{n}{k}2^k$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.