# Homework Help: Binomial coefficient question

1. Mar 25, 2010

### muso07

1. The problem statement, all variables and given/known data
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)

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

3. The attempt at a solution
First of all, I don't understand what {0,1}n 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}n.

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

Last edited: Mar 25, 2010
2. Mar 25, 2010

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