*From time to time, you stumble upon problems that are very simple yet not obvious, in
a way that makes them quite intriguing. Today, I’ve found one such problem as a subproblem
in a Codeforces round.*

Suppose you have two sets $A$ and $B$. Let’s say they are two teams of people, where each team can have a different size. You want to set up a fair match, with any number of people provided that both sides have the same number of players. For example, you can pick 1 player from $A$ and 1 from $B$, or 2 from each side, but not 1 from $A$ and 2 from $B$. In how many ways can you set up the match?

The formalized problem sounds simple: you want to count ways of pairing up equal-sized subsets from $A$ and $B$. Of course, one way of calculating the solution would be to simply evaluate the sum:

$$f(A, B) = \sum_{i=0}^{\min(|A|, |B|)} \binom{|A|}{i} \times \binom{|B|}{i}$$

But that is a lot of computation to do, and suppose we need to do better than that. There is a very elegant solution, which is also faster. If you want to think about it for a bit, now is the time. Otherwise, keep reading.

We can solve the problem by computing only **one** combination. I’ll first
give the formula, and then explain why it works. Let’s assume, without loss of generality,
that $|A| \leq |B|$. Then,

$$f(A, B) = \binom{|A| + |B|}{|A|}$$

Why does that make sense? What we’re doing here is, from all elements of $A$ and $B$
combined, choosing which elements of $B$ we are going to use, and at the same time which
elements of $A$ we going to **leave out** of our match. For example, say $A$ has 5
elements, and $B$ has 8. Let’s line them up:

$A_1\hspace{1em}A_2\hspace{1em}A_3\hspace{1em}A_4\hspace{1em}A_5\hspace{1em}B_1\hspace{1em}B_2\hspace{1em}B_3\hspace{1em}B_4\hspace{1em}B_5\hspace{1em}B_6\hspace{1em}B_7\hspace{1em}B_8$</

Now suppose we chose the following 5 elements in bold:

$A_1\hspace{1em}\textbf{A}_2\hspace{1em}\textbf{A}_3\hspace{1em}A_4\hspace{1em}\textbf{A}_5\hspace{1em}B_1\hspace{1em}B_2\hspace{1em}\textbf{B}_3\hspace{1em}B_4\hspace{1em}B_5\hspace{1em}B_6\hspace{1em}B_7\hspace{1em}\textbf{B}_8$

If we erase the bold from $A$ and keep only the bold $B$ elements, we get the following match:

$A_1\hspace{1em}A_4\hspace{1em}\texttt{vs}\hspace{1em}B_3\hspace{1em}B_8$

See? The elements chosen in $A$ were erased, and the elements chosen in $B$ were kept. This will always lead to a valid pair of subsets. To see why, suppose we pick $k$ elements from $A$: then we must have picked $|A| - k$ elements from $B$. That means we are going to keep $|A| - k$ elements from $A$ as well, after we erase $k$. Since $k \leq |A|$, and we assumed $|A| \leq |B|$, $0 \leq |A| - k \leq |B|$: both sides are valid. It’s also easy to see that, given a valid pair of subsets, there is only one way of choosing its elements with our procedure. Hence, this only combination gives us what we want.

$$\tag*{$\blacksquare$}$$