1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: Set theory question

  1. Nov 12, 2007 #1
    1. The problem statement, all variables and given/known data

    Prove that, for all n, for all m with 0 <= m <= n, the number of subsets of {1, . . . , n} of size m is the same as the number of subsets of {1, . . . , n} of size n − m.

    2. Relevant equations

    3. The attempt at a solution
    My problem is that I don't know where to begin. I have a vague notion that I should somehow find the powerset of all the sets of size m and n - m and compare their sizes. But I don't really know where to start.
  2. jcsd
  3. Nov 12, 2007 #2


    User Avatar
    Science Advisor
    Homework Helper

  4. Nov 12, 2007 #3
    C(n,m)=C(n,n-m) since order of elements in a set is not important.
  5. Nov 12, 2007 #4
    I am not familiar with combinations... what are they?

    A google search doesn't net me any useful results.
    Last edited: Nov 12, 2007
  6. Nov 13, 2007 #5

    matt grime

    User Avatar
    Science Advisor
    Homework Helper

    I want to choose m things. Therefore, I don't choose how many things?
  7. Nov 13, 2007 #6


    User Avatar
    Science Advisor

    If A is a subset of S= {1, 2,... n} with m members, how many members does S\A have? Do you see an obvious one-to-one correspondence?
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook