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

TalonStriker
Messages
14
Reaction score
0

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.
 
Physics news on Phys.org
Combinations?
 
C(n,m)=C(n,n-m) since order of elements in a set is not important.
 
EnumaElish said:
Combinations?

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

A google search doesn't net me any useful results.
 
Last edited:
I want to choose m things. Therefore, I don't choose how many things?
 
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?
 

Thread 'Prove that the integral is equal to ##\pi^2/8##'

Prove $$\int\limits_0^{\sqrt2/4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx = \frac{\pi^2}{8}.$$ Let $$I = \int\limits_0^{\sqrt 2 / 4}\frac{1}{\sqrt{x-x^2}}\arcsin\sqrt{\frac{(x-1)\left(x-1+x\sqrt{9-16x}\right)}{1-2x}} \, \mathrm dx. \tag{1}$$ The representation integral of ##\arcsin## is $$\arcsin u = \int\limits_{0}^{1} \frac{\mathrm dt}{\sqrt{1-t^2}}, \qquad 0 \leqslant u \leqslant 1.$$ Plugging identity above into ##(1)## with ##u...
View full post »

Similar threads

Prove every subset of countable set is either finite or else countable
Replies
1
Views
2K
How many subsets of size three or less are in a n-object set
Replies
4
Views
2K
Prove that every subset ##B## of ##A=\{1,...,n\}## is finite
Replies
4
Views
1K
Proving Completeness property of ##\mathbb{R}## using Dedekind cuts
Replies
20
Views
4K
Problem on a set which is a subset of a finite set
Replies
3
Views
1K
Every subset of a finite set is finite
Replies
1
Views
2K
Proving intersection of finitely many open sets is open
Replies
1
Views
2K
Person i belongs to a clique iff ith diagonal entry of B^3 is positive
Replies
9
Views
1K
Prove ##a \cdot 1 = a = 1 \cdot a## for ##a \in \mathbb{N}##
Replies
1
Views
1K
Prove ##1 + a=s(a)=a+1## for ##a \in \mathbb{N}##
Replies
1
Views
1K

Hot Threads

Recent Insights

Back
Top