Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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? –  EuYu Nov 5 '12 at 4:38
add comment

3 Answers

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"?

share|improve this answer
    
Dear wj32, I'm having difficulty understanding the idea of 'k coordinates equal to 1' and being 'switched on'. Could you elaborate this? –  Julian Park Nov 5 '12 at 4:53
    
@JulianPark: I'm assuming you've found the bijection in part a). Let $S=f([a_1,\dots,a_n])$. Each bit $a_i$ decides whether the number $i$ is to be included in $S$. If exactly $k$ of the $a_i$ are set to 1, then the size of $S$ is $k$. Therefore the answer to part c) is "all subsets of $\{1,\dots,n\}$ of size $k$". –  wj32 Nov 5 '12 at 5:10
add comment

Hint: You are in a cafeteria, at the end of the lunch hour. There is one Type $1$ item left, and one Type $2$ item, and one Type $3$ item, and so on up to one Type $n$ item. You are allowed to put on your tray $0$ or $1$ Type $1$ items, $0$ or $1$ type $2$ items, and so on.

You decide to plan lunch ahead of time, by writing down a sequence of $0$'s and/or $1$'s. So for example if $n=5$, and you write the sequence $01101$, that means you plan to say no to Item $1$, yes to Items $2$ and $3$, no to $4$, and yes to $5$. Note that the sequence $00000$ is a valid one: maybe you are on a diet.

Every sequence of $n$ $0$'s and or $1$'s represents a choice of meal. (That includes the empty meal.)

For (c), a sequence is in $S_k$ if and only if you have decided to have a $k$-item meal. For (d), how many ways are there to choose $k$ items for your meal, from the $n$ items available?

If you are not hungry, you are a teacher. The $n$ students are lined up in a row. You decide to choose "some" of them (possibly all, possibly none) to get a prize. You write down a sequence of $0$'s and/or $1$'s to record which students will get a prize. So for example if the line has $n=5$ students, $01101$ means the first student won't get a prize, the next two will, and so on. Each sequence uniquely determines the subset of the students who will get a prize.

share|improve this answer
    
Choosing k items for your meal from n items available would be n choose k (sampling without replacement)? –  Julian Park Nov 5 '12 at 5:02
    
@JulianPark: Yes, there are exactly $\binom{n}{k}$ ways to get a $k$-tem meal, just like there are $\binom{n}{k}$ ways to choose the $k$ positions that get a $1$. There are also, not coincidentally, $\binom{n}{k}$ subsets of size $k$. –  André Nicolas Nov 5 '12 at 5:05
add comment

For a), let's say that $n=2$, so you have the following binary strings: $\{0,0\}$, $\{1,0\}$, $\{0,1\}$ and $\{1,1\}$. We know that the power set, $P(\{1,2\})$ has elements empty set, $\{1\}$, $\{2\}$ and $\{1,2\}$. They are bijective (both have $4$ elements).

Now, to describe the function.

$f:\{0,0\} \to \emptyset$,

$f:\{1,0\} \to \{1\}$,

$f:\{0,1\} \to \{2\}$,

$f:\{1,1\} \to \{1,2\}$.

So, we can see that the places with $1$ correspond to the element from the set of the power set (I'll call it set $A$) is being applied to. (i.e, $f$ maps $\{0,1\}$ to the second element of $A$, namely $\{2\}$).

In general, for $n$,

$f:\{0\}^n \to \emptyset$,

$f: \{1\} \cup \{0\}^{n-1} \to \{1\}$,

$f: \{0,1\} \cup \{0\}^{n-2} \to \{2\}$,

$\ldots$

I believe this is the best way to describe the bijective function.

The inverse when $n=2$ is simply:

$f^{-1}:\emptyset \to \{0,0\}$,

$f^{-1}:\{1\} \to \{1,0\}$,

$f^{-1}:\{2\} \to \{0,1\}$,

$f^{-1}:\{1,2\} \to \{1,1\}$.

For c), restricting $f$ by $S_k$, we know that if there are $k$ $1$'s, then there are $k$ elements from set $A$ in the $f$ by $S_k$. This means that there will only be sets with $k$ elements in them present in the restriction (i.e., if $k=2$ and $n=2$, then $\{1,1\}$ will be the only element of the restriction $f$ by $S_k$). So the range is all sets with $k$ elements, i.e., n choose k elements.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.