# Set theory question

1. Nov 12, 2007

### TalonStriker

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
n/a

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. Nov 12, 2007

### EnumaElish

Combinations?

3. Nov 12, 2007

### andytoh

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

4. Nov 12, 2007

### TalonStriker

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

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

Last edited: Nov 12, 2007
5. Nov 13, 2007

### matt grime

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

6. Nov 13, 2007

### HallsofIvy

Staff Emeritus
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?