Tuesday, 5 July 2016

combinatorics - Counting subset of a finite set



Let $S=\{1,2,3,4,\cdots, n\}$. For any subset $T\subset S$, define
$$ P_k(T)=\left\{ V\subset T \ | \ \#(V)=k \right\} $$

that is the set of all subsets of cardinality $k$. Now for some fixed $\ell$ satisfying $1\leq \ell and for some collection of pairwise distinct $T_1,T_2,\ldots, T_m\in P_{\ell+1}(S)$, I would like to calculate all possible values of
$$\#\left(P_{\ell}\left(\bigcup_{i=1}^m T_i \right)\right). $$



My attempt:
First notice that
$$\#\left(P_{\ell}\left(\bigcup_{i=1}^m T_i \right)\right) =\#\left( \bigcup_{i=1}^m T_i \right) \ \text{ choose } \ell $$
so that it suffices to compute all possible values of $\#\left( \bigcup_{i=1}^m T_i \right)$. 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 $T_i$ 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 $\ell$.


Answer




Let $t=\#\bigcup T_i$.
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

real analysis - How to find $lim_{hrightarrow 0}frac{sin(ha)}{h}$

How to find $\lim_{h\rightarrow 0}\frac{\sin(ha)}{h}$ without lhopital rule? I know when I use lhopital I easy get $$ \lim_{h\rightarrow 0}...