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.

  • $\begingroup$ 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. $\endgroup$ – Batominovski Nov 7 '18 at 11:33
  • $\begingroup$ Some of your notation is a bit strange. What is $X!$ or $(X-m)!$? Do you mean $|X|$? $\endgroup$ – Michael Burr Nov 7 '18 at 11:34
  • $\begingroup$ Sorry, yes I mean $|X|$, edited it $\endgroup$ – JavaTeachMe2018 Nov 7 '18 at 11:36
  • $\begingroup$ 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. $\endgroup$ – Batominovski Nov 7 '18 at 11:36
  • $\begingroup$ Where is the inequality following the statement "So it follows that" coming from? This makes the result appear circular. $\endgroup$ – Michael Burr Nov 7 '18 at 11:38

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.