0
$\begingroup$

I am just learning about the inclusion exclusion principle while studying basic combinatorics. But I'm finding it extremely difficult to solve problems involving the inclusion exclusion principle mainly because I don't fully understand the principle behind it and also I am not able to detect which problems require the application of this principle.

Pls someone help, preferably with some examples. U don't know how much trouble this particular concept is giving me

Improve this question
$\endgroup$
1
$\begingroup$

You use it whenever you need to count elements of a union while you have information about their numbers in each part.

All you need to do is to draw Venn diagrams for two and for three sets.

For two sets:

Venndiagram2

How many elements are there in total?

The number of elements of $A$ plus the number of elements of $B$, but since the elements in the intersection have been counted twice, we substract the number of elements in the intersection once, to get them counted just once.

For three sets:

Venn3

How many elements in the total?

the number in $A$ plus the number in $B$ plus the number in $C$. But the elements in the intersections have been counted many times. Let us subtract the number of elements in pairwise intersections. This makes elements in the intersections $A\cap B$, $A\cap C$, $B\cap C$ to be counted once. But now the elements in $A\cap B\cap C$ have been subtracted completely because they were counted in all pairwise intersections. We add them back. We add the number of elements in $A\cap B\cap C$.

Improve this answer
$\endgroup$
  • $\begingroup$ Can u explain with a combinatorics problem, pls like derangement problems? $\endgroup$ – user34304 Jan 20 '14 at 13:12
  • $\begingroup$ @user34304 Yes, pls explain me how to solve all problems in mathematics. Do you have a red pill I can drink to be able to solve them all? Draw pictures. See what is the set you want to count. Can you divide it in parts that you know how to count? E.g. Count the arrangements fixing $1$. Then the arrangements fixing $2$. ... Then the arrangements fixing $1$ and $2$, ... If you know the totality of all arrangements that fix some elements you can subtract it from all permutations and get the derangements. $\endgroup$ – OR. Jan 20 '14 at 13:17
  • $\begingroup$ If u don't want to help, just say so sir. $\endgroup$ – user34304 Jan 20 '14 at 13:40
  • $\begingroup$ @user34304 I just wrote a long explanation of how to use inclusion-exclusion and an explanation on how to compute the number of derangements. $\endgroup$ – OR. Jan 20 '14 at 14:02
  • $\begingroup$ Ok, sorry sir. I was really frustrated $\endgroup$ – user34304 Jan 20 '14 at 14:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.