# Set theory question

## 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.

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.

## Answers and Replies

EnumaElish
Science Advisor
Homework Helper
Combinations?

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

Combinations?

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

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

Last edited:
matt grime
Science Advisor
Homework Helper
I want to choose m things. Therefore, I don't choose how many things?

HallsofIvy
Science Advisor
Homework Helper
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?