Let $B_n$ = $\mathcal{P}(\{1, 2, \dots, n\})$.
The set $\{0,1\}^n = \{a_1, a_2, … , a_n : a_i \in \{0,1\}\}$ is called the length of binary sequences of length $n$.
I want to verify and work on the following questions:
a) Describe a function $f:\{0,1\}^{n} \to B_n$ (which is a bijection), and give its inverse.
My attempt was as follows: Because this is a bijection, this would imply a one-to-one correspondence between the domain and the target set. Therefore, this function maps maps a binary sequence of length $n$ to the power set of length $n$.
I assumed that $f^{-1}: B_n \to \{0,1\}^{n}$ would be true.
b) Using part a, determine $|B_n|$.
Because $B_n$ = power set of $\{1, 2, \dots , n\}$, I claimed that the cardinality would be $2^n$.
c) Let $S_k$ be the set of elements of $\{0,1\}^{n}$ which have exactly $k$ coordinates equal to 1. Determine the range of the restriction of $f$ to $S_k$.
d) Determine $|S_k|$.
Best Answer
a) I think here "describe" means "give a specific example of". Hint: for a given subset $S$ of $\{1,\dots,n\}$, an element of $\{1,\dots,n\}$ is either in $S$ or not in $S$.
b) That's correct.
c) For this you need part a). What is the size of the set $f([a_1,\dots,a_n])$ if there are $k$ coordinates switched "on"?