2

How many eight-bit strings have exactly three $1$’s?

The answer is $8\choose 3$. Since we count subsets here, how can we set up a one-to-one correspondence between any $8$bit list with only three $1$s and some set? Consider the list $11100000$. Can we set up a correspondence like $11100000 \leftarrow \rightarrow \{123\}$ where the elements of the set are the numbers of the positions of ones? Since the $i$th position is fixed and named it doesn't matter if it comes before $i +1$th position in the set or after $i - 1$th position in the set, that is, $\{123\} = \{213\} = \{312\}$. All this is to say that we are allowed to encode a list as a set according to the rule above. Does that make sense?

Ace
  • 23
  • You can generalize this to a bijection between an $n$-length binary string with $1$ appearing $k$ times and a $k$-element subset $S$ of the set of integers between $1$ and $n$. The bijection (mapping subsets to binary strings) would look like $f(S)=a_{1}a_{2}...a_{n}$, where $a_{i}=\begin{Bmatrix} 0 & i\notin S\ 1 & i\in S \end{Bmatrix}$. You should be able to see that the number of $n$-bit strings where $1$ appears exactly $k$ times is the same as the number of ways to select a $k$-element subset from $\left [ n \right ]$. – Fred Jun 12 '15 at 01:13
  • 1
    In short, yes, that all makes sense. – pjs36 Jun 12 '15 at 01:24

0 Answers0