1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics proof question

  1. Mar 13, 2013 #1

    hm8

    User Avatar

    1. The problem statement, all variables and given/known data
    phpKzwJT9.png


    2. Relevant equations

    [itex]{a \choose b} = \frac{a!}{(a-b)!b!}[/itex]


    3. The attempt at a solution

    So I tried doing a mathematical induction proof (Show that it is true for some number, then show that if you assume it's true for 'k', it implies 'k+1')

    I was able to get the initial step, to show that they are equal when k=1.

    http://i.snag.gy/hss6O.jpg

    But I'm stuck now. The math get impossibly messy and unworkable when trying to do the inductive step. If I could think of a actual situation (like choosing committees/chairmen) that could be counted either way, I could use a combinatorial proof, but I'm having trouble coming up with one.
     
  2. jcsd
  3. Mar 13, 2013 #2

    Bacle2

    User Avatar
    Science Advisor

    Maybe you can see it this way ( sorry, I don't have time at the moment to look it thru carefully):

    You are choosing 2k+1 members out of n by selecting 2k members overall--after

    the 2k members have been selected, the extra one can only be the remaining one out

    of the 2k+1 , and you are selecting your 2k elements from two pools of elements

    ( people; people, elements, potato-potatoe) first (i=k+1) you select from k in one

    group and select the others from (n-k-1) others. Hope this can get you on the

    right track.

    select k out of
     
  4. Mar 13, 2013 #3

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    hi hm8! :smile:

    forget induction, you can do this directly!

    the LHS is the number of ways of choosing 2k+1 objects from n

    the RHS looks a lot like the number of ways of choosing 2k objects from n-1

    hint: where is the missing object? and what is i ? :wink:
     
  5. Mar 13, 2013 #4

    Bacle2

    User Avatar
    Science Advisor

    Don't you mean what am i (sorry for the horrible joke)?
     
  6. Mar 13, 2013 #5

    hm8

    User Avatar

    Still not quite getting it.

    I understand that the LHS is the number of ways of choosing 2k+1 objects from n -- thats straightforward enough.

    I think its the summation on the RHS thats confusing me. So for each step of the summation I'm choosing k things from two groups; k from a group that has one less than i objects in it, and then k more from a group that is i objects less than n. And I see that i goes from one more than k to n minus k in the summation...so the number of thing's were summing up is (n-k)-(k+1)= n-2k-1?

    I guess I'm still really not seeing it
     
  7. Mar 13, 2013 #6

    tiny-tim

    User Avatar
    Science Advisor
    Homework Helper

    no

    the number of things we're summing is the sum of the bottom lines, ie 2k

    the number of things we're summing from is the sum of the top lines, ie n-1

    so, as i asked before, where is the missing one? and what is (or am) i ? :wink:
     
  8. Mar 13, 2013 #7

    Bacle2

    User Avatar
    Science Advisor

    Another way:

    You want to count the number of ways of selecting 2k+1 ,say, people, out of 2n .

    Then you do this by partitioning the 2n people into groups A,B with n-k≥ |A|,|B|≥k

    and |A|+|B|=n-1 . Then choose k people from each, and throw in the one left out

    (|A|+|B|=n-1).
     
  9. Mar 13, 2013 #8

    Bacle2

    User Avatar
    Science Advisor

    You want to choose 2k+1 objects from 2n. You partition the n-1 people into two groups

    adding to 2k ( i.e., you leave one out) . Then you select first :

    i) k from k in group 1
    ii) k from (n-k-1) in group 2 ( n-k-1+k =n-1)
    iii) Throw in the one you left out

    And then you increase group 1 by one person and decrease group 2 by 1 on each
    iteration, each group choosing k.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Combinatorics proof question
  1. Combinatorics proof (Replies: 9)

  2. Combinatorics Proof (Replies: 10)

  3. Combinatorics Question (Replies: 4)

  4. Combinatorics question (Replies: 2)

Loading...