1
$\begingroup$

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

  • 1
    For part a, you're asked to find a bijection, not to describe what a bijection is. What do you think would be a good correspondence between the power set and the set of binary strings?2012-11-05

3 Answers 3