combinatorics - Number of ways to choose $k$ subsets such that $B_1 cap B_2 cap cdot cdot cdot cap B_k = emptyset$.

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.