The Student Room Group
Uni students - Complete our survey >>
Uni students - Complete our survey >>
Uni students - Complete our survey >>

Inclusion-Exclusion!

ie.png

Hi guys,

Question is above. Part a was fine.

Now for part b, they want us to find the number of sets in B, that is |B|. But B isn't a union or intersection of the subsets, it's simply a collection of all subsets - how do we use the inclusion exclusion principle here? What are we taking the union off?

I always find these questions quite difficult - any help is appreciated!

Thanks.
Original post by hmark101

Now for part b, they want us to find the number of sets in B, that is |B|. But B isn't a union or intersection of the subsets, it's simply a collection of all subsets - how do we use the inclusion exclusion principle here? What are we taking the union off?

I always find these questions quite difficult - any help is appreciated!

Thanks.


The clue, to me, is the statement "there is at least one i such that". So there, could be 1, or 2, or 3,...

So, how many B's are there such that ∣A1∩B∣=3|A_1\cap B|=3, and then the rest of the AiA_i. Then you need to remove the double counted ones - see the inclusion/exclusion arising?
(edited 10 years ago)
Reply 2
Avatar for hmark101
hmark101
OP
Original post by ghostwalker
The clue, to me, is the statement "there is at least one i such that". So there, could be 1, or 2, or 3,...

So, how many B's are there such that ∣A1∩B∣=3|A_1\cap B|=3, and then the rest of the AiA_i. Then you need to remove the double counted ones - see the inclusion/exclusion arising?


Right... I sort of see where this is going.

Ok, so there are (n choose k) B's that satisfy condition (i) - that is, the size of a subset B must be k.

But we also need to satisfy condition (ii). This is the trouble I am having... how do we know how many satisfy (ii)?!
Original post by hmark101
Right... I sort of see where this is going.


Any selection of k elements will satisfy condition 1. It's condition 2 that my previous post was trying to get you to focus one.
Reply 4
Avatar for hmark101
hmark101
OP
Original post by ghostwalker
Any selection of k elements will satisfy condition 1. It's condition 2 that my previous post was trying to get you to focus one.


Yes - I understand. The trouble I am having is: how do we know how many B's there are that satisfy condition 2? I can't seem to work that out.
Original post by hmark101
Yes - I understand. The trouble I am having is: how do we know how many B's there are that satisfy condition 2? I can't seem to work that out.


This is where your inclusion/exclusion comes in.

As I said in my first post, start by considering how many B's exist such that |A1nB|=3

Quick Reply

Related discussions

Latest

Trending

Trending

Articles for you