Simplify binomial expression

Question

I have this expression $$\sum_{k=0}^{10} {30 \choose k}{30 \choose 10-k}$$

I studied Pascals triangle, and also the binomial coefficients, but didn't manage to figure out how to solve this one.

Answer 1

Using Vandermonde's identity follows:

$$\sum_{k=0}^{10} {30 \choose k}{30 \choose 10-k}={{60}\choose{10}}$$

A combinatorial proof of this identity is such that:

Given two sets $A_1$ ,$A_2$ with cardinality $30$ and we want to choose $10$ objects from these two sets, it can be done by choosing $k$ objects from the first set in ${30 \choose k}$ ways, and then by choosing the remaining objects ($10-k$) in ${30 \choose 10-k}$ ways, another way would be grouping the two sets $A_1$ ,$A_2$ in a single set and choosing $10$ objects from the new set with cardinality $\left|A_{1}\right|+\left|A_{2}\right|=30+30=60$.

Answer 2

For $2n\ge30,$

The coefficient of $x^{k+10-k}$ in

$$(1+x)^n\cdot(1+x)^n$$ will be $$\binom{2n}{10}$$

Here $n=30$

Answer 3

You can look at this combinatorially or through Pascal's triangle.

Combinatorially : Imagine picking a committee of $10$ people from $60$. Of these, $30$ are girls and $30$ are boys. Through the natural interpretation the answer is $\binom{60}{10}$.

However, note that you can pick $k$ girls out of $30$ in $\binom{30}k$ ways, then pick the rest from the boys in $\binom{30}{10-k}$ ways. Each combination leads to a unique committee, and $k$ tuns from $0$ to $10$. So the same answer is $\binom{60}{10} = \sum_{k=0}^{10}\binom{30}{k}\binom{30}{10-k}$

---

From Pascal's triangle : the numbe of ways of reaching a given point from the root using only down left/down right paths is given by the Pascal's triangle. This is easy to see by induction (can also be used as the definition).

Now, think of $\binom{30}{k}$ as the number of paths to $\binom{30}{k}$ from the root. Imagine any one such path. Now, imagine a path to $\binom{30}{10-k}$. For each $k$ this can be done.

Now we simply have a path to $\binom{60}{10}$, since joining the paths from $0$ to $\binom{30}k$ and then moving the second path to start at $\binom{30}k$ makes the end rest at $\binom{60}{10}$.

This clearly shows that each path from root to $(60,10)$ breaks into two parts : where it hits row $30$ and what happens after that. This leads naturally to (based on for which $k$ the path passes through $\binom{30}k$) the given identity.

Also note that $30,30$ was not special : all we required was two numbers adding up to $60$, each of which is greater than $10$, for the above logic to work k. So , for example, the same would also give you $\binom{60}{10} = \sum_{k=0}^{10}\binom{47}k\binom{13}{10-k}$.

---

The Pascal triangle approach can be used to give a proof of the general Vandermonde's identity.

$$ \binom{n_1+\ldots+n_p}{m} = \sum_{k_1+\ldots+k_p = m}\binom{n_1}{k_1}\ldots \binom{n_p}{k_p} $$

Indeed, take a down left/down right path from the root $0$ to $(n_1+\ldots+n_p,k)$. Look at the levels $n_1,n_1+n_2,\ldots$ and break the big path into $p$ small paths between these levels.

That's a bijective map : you can easily put back the small paths to get the big path, and the number of small paths is instantly seen to be the RHS, while the number of big paths is seen to be the LHS.