Set theory question

  • #1

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.
 

Answers and Replies

  • #2
EnumaElish
Science Advisor
Homework Helper
2,304
124
Combinations?
 
  • #3
359
3
C(n,m)=C(n,n-m) since order of elements in a set is not important.
 
  • #5
matt grime
Science Advisor
Homework Helper
9,395
4
I want to choose m things. Therefore, I don't choose how many things?
 
  • #6
HallsofIvy
Science Advisor
Homework Helper
41,833
964
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?
 

Related Threads on Set theory question

  • Last Post
Replies
1
Views
517
  • Last Post
Replies
2
Views
787
  • Last Post
Replies
1
Views
807
  • Last Post
Replies
3
Views
530
  • Last Post
Replies
3
Views
646
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
0
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
811
  • Last Post
Replies
1
Views
725
Top