How do I prove an equality by constructing a bijection

Question

I know how to do the problem conceptually, and proving the equality by computing isn't hard, but we are required to use a bijection to prove this, any ideas please?

https://i.stack.imgur.com/Q60pM.jpg

Answer 1

HINT:

Try to translate the formulas into combinatorical concepts i.e.:

$$ \binom{a}{b} $$

means the number of ways to choose $b$ things out of $a$ things without caring about the order of the choices.

Answer 2

Let $U$ be the set $\{1,2,\ldots,m+n\}$, $V=\{1,\ldots,m\}$ and $W=\{m+1,\ldots,m+n\}$.

Now define $\mathcal P_j(A)$ as the set of subsets of some set $A$ that have exactly $j$ elements.

Consider $$f:\bigcup_{i=0}^k[\mathcal P_i(V)\times\mathcal P_{k-i}(W)]\to\mathcal P_k(U)$$ as $$f(A,B)=A\cup B$$