Binomial coefficients and words of $n$ bits, why this works?

Question

I read this on a webpage about the binomial coefficients:

If $\{0,1\}$ are bits and $k$ is the amount of "ones" ${n}\choose{k}$ gives the quantity of strings of length $n$ which have exactly $k$ ones in it.

Why is this true? I thought until now that the binomial coefficient ${a}\choose{b}$ gave only informations about the numbers of ways you can choose a subsets of cardinality $b$ from one whose cardinality is $a$.

Answer 1

Consider the following transformation: let $B$ be a set of cardinality $b$ and let us represent a subset $A$ of $B$ as a binary string of length $b$ with a one if the corresponding element is taken and a zero otherwise.

E.g. $$B=\{ u, v, w, x, y, z\}$$

$$A=\{ u, v, z\}\leftrightarrow 110001.$$

Now how many strings of length $b$ having $a$ ones are there ?

Answer 2

Let's rephrase the problem as the number of ways that a sequence of length $n$ can have $k$ ones.

In some sense, this becomes a combinatorics problem since we are selecting $k$ positions out of the $n$ to be "ones", and the rest to be zeros.

So, that explains why the result is ${n}\choose{k}$, since we are $\textit{choosing}$ $k$ ones from $n$ positions.

Answer 3

Here's a bijective argument, let $\mathcal{P}_k([n])$ be the set of subsets of $\{1, \dots, n\}$ of size $k$, and let

$$ S = \{(b_1, \dots, b_n) \in \{0,1\}^n \ | \ \#\{i \in [n] : b_i = 1\} = k\} $$

Now, the mapping

$$ \Lambda: \mathcal{P}_k([n]) \longrightarrow S \\ A \mapsto \Lambda(A) $$

with

$$ \Lambda(A)_i := \cases{1 \text{ if } i \in A\\0 \text{ if } i \not \in A} $$

is bijective.

In effect, if $A \neq B$, wlog there exists $j \in A$ such that $j \not \in B$. Thus, $\Lambda(A)_j = 1 \neq 0 = \Lambda(B)_j$ and so $\Lambda(A) \neq \Lambda(B)$ which proves that $\Lambda$ is injective. Finally, if $b \in S$, you can check that $A_b := \{j \in [n] : b_j = 1\}$ has size $k$ and verifies $\Lambda(A_b) = b$.