Proving Set Theory Equation: Subsets of Size m = Subsets of Size n-m

[TalonStriker]

Homework Statement

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.

Homework Equations

n/a

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.

 

[EnumaElish]

Combinations?

 

[andytoh]

C(n,m)=C(n,n-m) since order of elements in a set is not important.

 

[TalonStriker]

Combinations?

I am not familiar with combinations... what are they?

A google search doesn't net me any useful results.

 

[matt grime]

I want to choose m things. Therefore, I don't choose how many things?

 

[HallsofIvy]

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?