Problem: Compute $\sum_{m=0}^{2009} \sum_{n=0}^m\binom{2009}{m}\binom{m}{n}$ Solution: This problem is simply a mask of [[Pairs of (A,B) where A is in B is in S]]. In this problem let $S$ be such that $|S| = 2009$. We ask, how many tuples of sets $(A,B)$ are there so that $A \subseteq B \subseteq S$. One method to count this is the above where we vary over all possible sizes of $B$ with $m$ and then vary over all possible sizes of $A$ by choosing $n$ from the $m$ elements of $B$. Another way to count this is by noticing the followng: we may construct a valid $(A,B)$ provided each element of $S$ satisfies one of three properties (which can be encoded as a $0,1,2$): - $x \in S$ and $x \in A$ and $x \in B$ - $x \in S$ and $x \not\in A$ and $x \in B$ - $x \in S$ and $x \not\in A$ and $x \not\in B$ So, there are $3$ choices for each $x \in S$ and we see vaguely (but rigorously enough) that there is a bijection between the set of all such $(A,B)$ and the number of $2009$-length ternary strings. So, the sum is $3^{2009}$.