Combinatorial set theory: finding the cardinality of a set

72 Views Asked by At

For an integer $0 \leq k \leq 2^{N-m}$, and an alphabet $\Sigma = \{0, 1\}$, define a set of sets $B_{k}$ as

$$B_{k} = \{ B \subseteq \{0, 1\}^{n} : |\{x \in \Sigma^{N-m} : x \Sigma^{m} 0^{n-N} \subseteq B \}| = k \}.$$

How many distinct sets are there in $B_{k}$?

I have tried for $B_{0}$. If we put similar strings in buckets, there are $2^{N}$ strings of the form $\Sigma^{N} 1^{n - N}$ in one bucket and $2^{m}$ distinct buckets of $2^{N-m}$ strings each. Now, I can create a $B \in B_{0}$ by putting together strings of the first bucket and strings of any of the other $2^{m} - 1$ buckets (but not all $2^{m}$ of them at the same time). However, this gives rise to a very complicated structure which I do not know how to simplify. I also do not know how to generalize it for higher values of $k$.