2
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$ Jun 18, 2017 at 22:40

1 Answer 1

1
$\begingroup$

$|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|$.

$\endgroup$
2
  • $\begingroup$ Aha, thanks, that's true. However, I still can't see how $|D-E| = r-i$ and so on. $\endgroup$ Jun 18, 2017 at 6:13
  • $\begingroup$ @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. $\endgroup$ Jun 18, 2017 at 12:22

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .