How Does the Binomial Coefficient Relate to Subsets of Binary Sequences?

[muso07]

Homework Statement

Show that: $$(\stackrel{n}{k})=\#\left\{(\omega_{1},..., \omega_{n})\in\left\{0,1\right\}^{n}:\Sigma^{n}_{l=1}\omega_{l}=k\right\}$$

(edit: the sigma is meant to go from l=1 to n)

Homework Equations

It says to use this:
$$(\stackrel{n}{k})=\#\left\{M\subseteq\left\{1,...,n\right\}:\#M=k\right\}$$

The Attempt at a Solution

First of all, I don't understand what {0,1}ⁿ is. Like, I think I should be able to nut this problem out if I understood that.. so I don't really need help with the actual question (yet :P), but I need help with the definition of {0,1}ⁿ.

The only thing I could find was $$\left\{0,1\right\}^{n}=\left\{(\omega_{1},...,\omega_{n}):\omega_{k}\in\left\{0,1\right\}, 1\leq k\leq n\right\}$$

And I don't really get that...

 

[ystael]

$$\{0, 1\}^n$$ is the Cartesian product of $$n$$ copies of the set $$\{0, 1\}$$, that is, $$\{0, 1\} \times \{0, 1\} \times \cdots \times \{0, 1\}$$ (with $$n$$ factors). This is the set of $$n$$-tuples where each entry belongs to $$\{0, 1\}$$; the entries look something like $$(0, 1, 1, 0, \dots, 0)$$. This is what the notation $$\{0, 1\}^n = \{ (\omega_1, \dots, \omega_n) \mid \omega_k \in \{0, 1\}, 1 \leq k \leq n \}$$ means: $$\{0, 1\}^n$$ is the set of $$n$$-tuples $$(\omega_1, \dots, \omega_n)$$ where each of the $$\omega_k$$ belongs to $$\{0, 1\}$$.

Incidentally, you can write $$\binom{n}{k}$$ as \binom{n}{k}.