# Proving $|Z| \leq \binom{n}{l}/ \binom{m}{l}$

Let $$l \leq m$$. Let $$X$$ be a set $$|X| = n$$ and $$Z \subseteq \binom{X}{m}$$, so that for every set $$L \in \binom{X}{l}$$ there is at most one set $$B \in Z$$ with $$L \subseteq B$$. How can one prove the following: $$|Z| \leq \frac{\binom{n}{l}}{\binom{m}{l}}\,?$$

I did the following and I'd like to know if it is correct or not.

$$\binom{n}{l} =\frac{n!}{l!(n-l)!}$$ and

$$\binom{m}{l} =\frac{m!}{l!(m-l)!}\,.$$

Dividing both:

$$\frac{\frac{n!}{l!(n-l)!}}{\frac{m!}{l!(m-l)!}} = \frac{n!}{l!(n-l)!} \cdot \frac {l!(m-l)!}{m!}\,.$$

Since $$Z \subseteq \binom{X}{m}$$, we can say that $$Z \subseteq \frac{X!}{m!(X-m)!}\,,$$

so it follows that

$$\frac{X!}{m!(X-m)!} \leq \frac{n!}{l!(n-l)!} \cdot \frac {l!(m-l)!}{m!}\,.$$

We can divide by $$\frac {l!(m-l)!}{m!}$$

and get

$$\frac{X!}{m!(X-m)!} \cdot \frac {m!}{l!(m-l)!} \leq \frac{n!}{l!(n-l)!}\,.$$

We can cancel $$m!$$ and get

$$\frac {|X|!}{(|X|-m)! \cdot l!(m-l)!} \leq \frac{n!}{l!(n-l)!}\,.$$

Since $$|X| = n$$, we can write

$$\frac {n!}{(n-m)! \cdot l!(m-l)!} \leq \frac{n!}{l!(n-l)!}\,,$$

which is true, because the bigger the denominator gets, the smaller the number.

• While the notation $\displaystyle \binom{X}{m}$ makes sense, the expression $\dfrac{X!}{m!\, (X-m)!}$ does not make sense, since $X$ is a set, not a number, let alone comparing such an expression with a number. – Batominovski Nov 7 '18 at 11:33
• Some of your notation is a bit strange. What is $X!$ or $(X-m)!$? Do you mean $|X|$? – Michael Burr Nov 7 '18 at 11:34
• Sorry, yes I mean $|X|$, edited it – JavaTeachMe2018 Nov 7 '18 at 11:36
• And the last inequality is wrong. The inequality is equivalent to $$(n-l)!\leq (n-m)!\,(m-l)!\,,$$ which is identical to $$\binom{n-l}{m-l}\leq 1\,.$$ This is false for large $n$, of course. Therefore, I am sorry to say that your proof is incorrect. – Batominovski Nov 7 '18 at 11:36
• Where is the inequality following the statement "So it follows that" coming from? This makes the result appear circular. – Michael Burr Nov 7 '18 at 11:38

## 1 Answer

Define $$S:=\Biggl\{(L,B)\in \binom{X}{l}\times Z\,\Big|\,L\subseteq B\Biggr\}.$$ Since for each $$\displaystyle L\in \binom{X}{l}$$, there exists at most one $$B$$ in $$Z$$ for which $$L\subseteq B$$, we have $$|S|\leq \Biggl|\binom{X}{l}\Biggr|=\binom{n}{l}\,.$$ Now, each $$B\in Z$$ has $$m$$ elements, and therefore, there are $$\displaystyle\binom{m}{l}$$ subsets $$\displaystyle L\in\binom{X}{l}$$ such that $$L\subseteq B$$. This shows that $$|S|=\binom{m}{l}\,|Z|\,.$$ The claim follows immediately.