# Combinatorics - Counting in two ways? [duplicate]

What is the idea of proving a binomial identity by counting in two ways?

Could you please illustrate this with this example? Thank you very much.

$$\binom{2n}{n}= \sum_{k=0}^n {\binom nk}^2$$

(original screenshot)

-

## marked as duplicate by Marc van Leeuwen, Sami Ben Romdhane, Claude Leibovici, Davide Giraudo, Mark BennetMay 2 '14 at 7:11

This becomes a special case of the Vandermonde identity if you replace one of the factors $\binom nk$ by $\binom n{n-k}$. Also, it is a duplicate of at least this question, if not of many others. – Marc van Leeuwen May 2 '14 at 5:28

The idea behind the technique is to perform the same task using procedures that are distinct. From each distinct procedure, we obtain a combinatorial expression for the number of ways that the task can be performed. Since the same task was performed, the combinatorial expressions are the same.

The most simple example is probably the procedure that results in selecting $k$ objects from a collection of $n$ distinct objects. We might perform this task by first placing the $n$ objects on a table, marking $k$ of them as the objects to select, and then move the $k$ marked objects to a separate pile. There are $\binom{n}{k}$ ways to do this. Alternatively, we might look at our pile, and mark $n-k$ objects to not select, and then move the remaining $k$ unmarked objects to a separate pile. There are $\binom{n}{n-k}$ ways to mark the $n-k$ objects to leave out of the collection. Since each procedure results in the same thing -- a collection of $k$ objects-- the number of ways to perform each procedure must be the same. Therefore, $$\binom{n}{k}=\binom{n}{n-k}$$

In your given example can think as follows. The left hand side $$\binom{2n}{n}$$ counts the number of ways to select $n$ objects from a collection of $2n$ objects. We could perform this task as above: place all objects on a table and mark $n$ of them to keep which gives the above expression. Alternatively, we could first split the pile of $2n$ objects into two separate piles of $n$ objects. To get the desired collection of $n$ objects, we could select $k$ from the first pile ($\binom{n}{k}$ ways), and the remaining $n-k$ from the second ($\binom{n}{n-k}$ ways). Thus, the number of ways to do so is: $$\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$$ Therefore, $$\binom{2n}{n}=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}$$ To get your desired result, simply use the identity established earlier to find that: \begin{align*} \binom{2n}{n}&=\sum_{k=0}^n\binom{n}{k}\binom{n}{n-k}\\ &=\sum_{k=0}^n\binom{n}{k}\binom{n}{k}\\ &=\sum_{k=0}^n\binom{n}{k}^2 \end{align*}

-
Puntuation never goes after TeX's double dollar sign! – Mariano Suárez-Alvarez May 2 '14 at 2:22
@Mariano Gracias, was just typing along without thinking. – Scott H. May 2 '14 at 2:24

[EDIT]

The idea behind double counting arguments is to provide verbal proofs of combinatorial identities that give an intuitive understanding of why they should be so. By simply showing that two expressions measure different ways to count the same thing it becomes clear to even a novice mathematician that they must be equivalent.

On the left hand side: $\binom{2n}{n}$ is the count of ways to divide a set of distinct objects into two equal sized subsets.

On the right hand side: $\sum\limits_{k=0}^{n} \binom{n}{k}^2$ is the count of ways to redistribute objects between two equal sized sets as follows:

$\binom{n}{k}$ counts the ways to select $k$ objects form a set of $n$ distinct objects. Thus $\binom{n}{k}^2$ counts the ways to do this for two sets; which makes it the count of ways to transfer $k$ object from one set to the other in exchange for $k$ objects originally in the second set. The summation is thus the count of ways to exchange equal numbers of distinct objects between two equal sized sets, for all possible size of the exchanges.

It should be clear that one gets the same result by simply combining the two sets and counting all the ways to split them into equal sized sets.

Hence it follows that: $\dbinom{2n}{n}=\sum\limits_{k=0}^{n} \dbinom{n}{k}^2$

-

An alternative proof is the following.

What is the coefficient of $x^n$ in $(1+x)^{2n}$?

Write this as $(1+x)^n(1+x)^n$. What is it now?

Note $$\sum_{k=0}^n\binom nk^2=\sum_{k=0}^n \binom nk\binom n{k -n}=\sum_{i+j=n}\binom ni\binom nj$$

-

Let $a$ = number of ways of choosing $n$ animals from $n$ cats and $n$ dogs is $\binom{2n}{n}$.

Let $c(k)$ = number of ways of choosing $k$ cats from $n$ cats = $\binom{n}{k}$

Let $d(k)$ = number of ways of choosing $n-k$ dogs from $n$ dogs = $\binom{n}{n-k}$ = $\binom{n}{k}$

Thus, $e(k)$ = number ways of choosing $k$ cats and $n-k$ dogs = $c(k)*d(k) = {\binom nk}^2$

Obviously $a$ = Number of ways of choosing $k$ cats and $n-k$ dogs for all $k \in [0, n]$

Therefore, $a = \sum_{k=0}^n e(k) = {\binom nk}^2$. QED.

-