Thread: Power set,bijection and binomial coefficient

Let N={1,2.....n} .Define the Power set of N,P(N), and show that the map f:P(N)->P(N)
defined by taking A to belong to P(N) to N\A is a bijection.
Also prove using the above that
(n)=(n)
(k-1) (k)

Now the power set is defined by P(N)=2^n and a bijection is a one-to-one function that is both injective and surjective.But I don't understand the rest.I"ve been looking at it for the past 1 hour.

Originally Posted by AkilMAI

Let N={1,2.....n} .Define the Power set of N,P(N), and show that the map f:P(N)->P(N)
defined by taking A to belong to P(N) to N\A is a bijection.

The LaTeX rendering is down at the present.
So let C(A) denote the complement of A in N={1,2,3,...,n}.
The proof that f is invective depends on the fact that C(C(A))=A.
That is also used to prove it is surjective.
If B is a subset of N, then f(C(B))=B.

That is an interesting ideea...I never thought of using the complement.How can I use that to prove the last binomial relation from the problem?I know that
(n)=(n-1) + (n-1)
(k) (k-1) (k)
but is states to use part a)

For part a) my ideea for to use the fact that the domain and range have the same cardinality since we are using the power set of N but I don't know how to expres this in a mathematical way that will be inteligible.

Originally Posted by AkilMAI

That is an interesting ideea...I never thought of using the complement.How can I use that to prove the last binomial relation from the problem?I know that
(n)=(n-1) + (n-1)
(k) (k-1) (k)
but is states to use part a)

First of all the notation N\A means the complement of A in N.

Let's use C(N,k) to mean combination of N taken k at a time.
And |A| is the number of elements in A.

|N\A|=n-|A|. BUT |A|=C(n,|A|).
Use the symmetry from part a).

I"m sorry maybe I'm just tired...but I"m more confused about both parts now that I was before.How can I use the complement in part a) to prove injection and surjection and what symmetry are you referring to?

Originally Posted by AkilMAI

I"m sorry maybe I'm just tired...but I"m more confused

Sorry, but I will not do this problem for you.
The last line in reply #2 proves that f is surjective.
For injectivity note that the complement of the complement is the original set.

BTW. In part b) you are to prove that C(n,k)=C(n,n-k). Not what you posted in the O.P.

Maybe you do get people asking you to do their problems for them but in this case that wasn't what I was implying...I was only saying that I got more confused.