Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Binomial coefficient question

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

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


    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 [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: Mar 25, 2010
  2. jcsd
  3. Mar 25, 2010 #2
    [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}.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook