Let $ \space n,k \in \mathbb Z \space $ such that $1 \le k \le n \space$. Let $\space A=\{1,2,...,n\}$. Find the number of ways to choose $k$ subsets $\space B_1,B_2,...,B_k\space $ of $A$ such that $ B_1 \cap B_2 \cap \cdot \cdot \cdot \cap B_k = \emptyset$.
Well, I did it using inclusion exclusion, but I'm wondering if this is possible using a recursive formula.
By inclusion exclusion: $\sum_{i=0}^n \binom{n}{i} (-1)^i (2^{n-i})^k$ and by binom $(2^k-1)^n$
Answer
Let $F(k,n)$ denote the answer you seek.
Note first that $F(k,1)=2^k-1$. to see this, we remark that the only two subsets are $\emptyset, \{1\}$. Thus in your list of $k$ we can choose freely from these two, but we can't choose $\{1\}$ every time.
Now consider $F(k,n)$. If you delete the element $n$ from every set (if it is there) you get a selection counted by $F(k,n-1)$. But starting from a selection of that form we can add $n$, or not, to each set, but we can't add it to every set. Thus $$F(k,n)=F(k,n-1)\times (2^k-1)$$ and we are done.
No comments:
Post a Comment