• Support PF! Buy your school textbooks, materials and every day products Here!

Binomial coefficient question

  • Thread starter muso07
  • Start date
  • #1
54
0

Homework Statement


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

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

Homework Equations


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


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 [tex]\left\{0,1\right\}^{n}=\left\{(\omega_{1},...,\omega_{n}):\omega_{k}\in\left\{0,1\right\}, 1\leq k\leq n\right\}[/tex]

And I don't really get that...
 
Last edited:

Answers and Replies

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

Incidentally, you can write [tex]\binom{n}{k}[/tex] as \binom{n}{k}.
 

Related Threads for: Binomial coefficient question

  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
2
Views
3K
  • Last Post
Replies
1
Views
645
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
1
Views
5K
  • Last Post
2
Replies
29
Views
6K
  • Last Post
Replies
1
Views
1K
Top