Tuesday, 5 July 2016

combinatorics - Counting subset of a finite set



Let S={1,2,3,4,,n}. For any subset TS, define
Pk(T)={VT | #(V)=k}

that is the set of all subsets of cardinality k. Now for some fixed satisfying $1\leq \ell and for some collection of pairwise distinct T1,T2,,TmP+1(S), I would like to calculate all possible values of
#(P(mi=1Ti)).



My attempt:
First notice that
#(P(mi=1Ti))=#(mi=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

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