$A_k=\{(w_1,w_2,...,w_n)\in \Omega^n: w_i=1 \text{ for exactly k indices}\}$ $\implies$ $|A_k|={n \choose k}$

Question

Could someone elaborate how the following implication is seen:

$$A_k=\{(w_1,w_2,...,w_n)\in \Omega^n: w_i=1 \text{ for exactly k indices}\}$$ $$\implies|A_k|={n \choose k}$$

where $\Omega = \{0,1\}$.

Answer 1

I assume that here $\Omega$ is the set $\{0,1\}$. To make a sequence of length $n$ with $k$ $1$'s, we need to choose the $k$ places where $1$'s will go. By the definition of the binomial coefficient $\binom{n}{k}$, this can be done in $\binom{n}{k}$ ways.

We now show that the answer is also given by $\frac{n!}{k!(n-k)!}$.

We look at the following problem: We have $n$ chairs lined up in a row. How many ways are there of seating $k$ people. We find the answer in two different ways.

Way 1: The youngest person can be seated in $n$ ways. For each of these ways, the second youngest person can be seated in $n-1$ ways. For each of these ways, the third youngest can be seated in $n-2$ ways, for a total of $n(n-1)(n-2)\cdots (n-k+1)$. Note that $$n(n-1)(n-2)\cdots (n-k+1)=\frac{n(n-1)(n-2)\cdots (n-k+1)(n-k)(n-k-1)\cdots (1)}{(n-k)(n-k-1)\cdots(1)}=\frac{n!}{(n-k)!}.$$ Thus we can seat our people in $\frac{n!}{(n-k)!}$.

Way 2: Choose $k$ of the chairs. This by definitin can be done in $\binom{n}{k}$ ways. Once we have chosen the set of $k$ chairs, the $k$ people can be arranged in these chairs in $k!$ ways, for a total of $\binom{n}{k}k!$.

Comparing the answers for Way 1 and Way 2, we see that $$\frac{n!}{(n-k)!}=\binom{n}{k}k!.$$

From this, by dividing both sides by $k!$, we get that $\binom{n}{k}=\frac{n!}{k!(n-k)!}$.