Let S={1,2,3,4,⋯,n}. For any subset T⊂S, define
Pk(T)={V⊂T | #(V)=k}
that is the set of all subsets of cardinality k. Now for some fixed ℓ satisfying $1\leq \ell
#(Pℓ(m⋃i=1Ti)).
My attempt:
First notice that
#(Pℓ(m⋃i=1Ti))=#(m⋃i=1Ti) choose ℓ
so that it suffices to compute all possible values of #(⋃mi=1Ti). The inclusion-exclusion principle states that
$$\#\left( \bigcup_{i=1}^m T_i \right)=\sum_{i=1}^m (-1)^{k+1}\left( \underset{1\leq i_1 < i_2 \ldots
Thus it suffices to count the ways in which the Ti can intersect. I can do this in specific case, but I do not know how to write this down for arbitrary fixed values n and ℓ.
Answer
Let t=#⋃Ti.
Then we must have {t\choose \ell+1}\ge m because we find m distinct (\ell+1)-subsets of S. This gives a lower bound t_0 for t, namely the first positive integer for which the polynomial X(X-1)\cdots(X-\ell) exceeds m\cdot (\ell+1)!. I am afraid, there is no closed form for this for general \ell, but you may find something nice for small \ell.
On the other hand t\le \min\{m(\ell+1),n\} because the first value holds for the extreme case of disjoint sets and the other comes from the fact that the union is still a subset of S.
No comments:
Post a Comment