# Understanding a one-to-one function with regards to a combinatorial equality

Show $$\sum_{i=0}^n \binom{n}{r-i} \binom{n-r+i}{s-i} \binom{n-r-s+2i}{i} = \binom{n}{r} \binom{n}{s}$$

For the LHS, we remove the sum for a second and look at the components. This equals the number of triples $(A,B,C)$ such that:

• $A \subset N_n, |A| = r-i$
• $B \subset N_n -A, |B| = s-i$
• $C \subset N_n - (A \cup B), |C| = i$

Then $|X_o \cup X_1 \cup \dots \cup X_n | = \sum_{i=0}^n \binom{n}{r-i} \binom{n-r+i}{s-i} \binom{n-r-s+2i}{i}$.

Now we do the same for the RHS:

• $Y = \{ (D,E): D \subset N_n, |D| = r, E \subset N_n, |E| =s \}$

Now we have to define a one-to-one correspondence to finish the exercise. We do it as follows:

• $f: X_o \cup X_1 \cup \dots \cup X_n \to Y: (A,B,C) \to ( A \cup B, B \cup C)$

I had more trouble with the inverse, and I found the following in the correction sheet:

• $f^{-1} : Y \to X_o \cup X_1 \cup \dots \cup X_n: (D,E) \to (D-E, E-D, D \cap E)$

I don't understand this however. $|D-E| = r -s \neq r -i ; |E-D = s-r \neq s-i$. So what gives?

• I would like to point out that this identity also has an algebraic proof. Hence I ask your permission to post this calculation. This is in order to comply with MSE etiquette. I will only post on a positive response since the proof is not combinatorial and hence not directly relevant to your question. It does feature useful techniques for binomial coefficient manipulation (Egorychev method). Jun 18, 2017 at 22:40

$|D - E| = |D - (D \cap E)| = |D| - |D \cap E|$ not $|D - E| = |D| - |E|$. In general, $|D - E| = |D| - |E|$ if and only if $E \subseteq D$.
For example if $D = \emptyset$ and $E = \{1\}$ then $|D| - |E| = -1$ and this certainly cannot be equal to $|D - E|$.
• Aha, thanks, that's true. However, I still can't see how $|D-E| = r-i$ and so on. Jun 18, 2017 at 6:13
• @YakSalTafri $i$ is the size of $D \cap E$ and can be any number between $0$ and $n$. If $D$ has $r$ elements then subtracting $E$ removes the $i$ common elements from $D$. This leaves $r - i$ elements. Jun 18, 2017 at 12:22