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