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

Gosh darn combinatorics

  1. Sep 14, 2014 #1
    So look at what Ive done:
    [tex]
    {n+1 \choose k} = \frac {(n+1)!} {(n+1-k)! \cdot k!} = \frac {(n+1)\cdot n!}{(n-(k-1))!\cdot k \cdot (k-1)!}
    [/tex][tex]
    =
    \frac {(n+1)}{k}


    \cdot

    \frac { n!}{(n-(k-1))!\cdot (k-1)!} =

    \frac {(n+1)}{k}

    \cdot


    {n \choose k-1}

    [/tex]



    oops I accidentally posted this before I finished my calculations, please ignore this until I've finished it. Thanks

    [edit] So Yea, thats it. Thing is, somethings wrong (try plugging numbers into it). Anyways, I need to figure out what I did wrong. This is just part of a massive can of worms. Im trying to figure out the proof for: [tex]


    \sum\limits_{i=1}^n {n \choose k} = 2^n
    [/tex]
     
    Last edited: Sep 14, 2014
  2. jcsd
  3. Sep 14, 2014 #2

    jedishrfu

    Staff: Mentor

  4. Sep 14, 2014 #3
    Pascals identity to be exact. I've read some "proofs" if you can call them that, but they were rather not helpful. math stack exchange.

    When I replace my summation from k=0 to n, with the combinatorics: [itex]

    \sum_{k=0}^n{n+1 \choose k} =

    \sum_{k=0}^n {n \choose k} +{n \choose k-1}

    [/itex] I have the problem that k-1 will equal -1 in the first iteration of the summation. dont know how to fix this.
     
  5. Sep 14, 2014 #4

    Mentallic

    User Avatar
    Homework Helper

    The lower limit of the sum should be k=0 because i isn't present in the combinatoric and for reasons you'll eventually find out, it should start at 0.


    So you want to prove
    [tex]
    \sum\limits_{k=0}^n {n \choose k} = 2^n
    [/tex]

    then simply notice that the binomial expansion is

    [tex](a+b)^n = \sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k[/tex]

    So for what values of a and b is

    [tex]\sum\limits_{k=0}^n{n\choose k}a^{n-k}b^k\equiv \sum\limits_{k=0}^n {n \choose k}[/tex]
     
  6. Sep 21, 2014 #5
    The problem here is that ##\binom{n+1}k=\binom nk+\binom n{k-1}## only for k>0; if k=0 then it's just ##\binom nk##, as both are 1. I think the convention is often to let ##\binom n{-1}=0##; then ##\binom{n+1}k=\binom nk+\binom n{k-1}## even when k=0.
     
  7. Sep 22, 2014 #6

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    You are right that the proof by induction approach can turn into a can of worms.
    Notice that [itex]
    \sum\limits_{k=0}^n {n \choose k}
    [/itex] is the total number of ways that any number of items (including 0 and n) can be selected from n items.

    If we indicate whether an item is selected or not by 1 or 0, respectively, and put the 1's and 0's in order, we can represent any set of selected items.

    For instance, starting with n=5 items, 10110 = select first, don't select second, select third, select fourth, don't select fifth, represents one way of selecting 3 of the 5. Now, how many zero/one patterns can we get from 5 binary digits?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Gosh darn combinatorics
  1. Combinatorics problem (Replies: 14)

  2. Combinatorics question (Replies: 1)

  3. Combinatorics question (Replies: 3)

  4. Combinatorics problem (Replies: 2)

Loading...