Derangements/Inclusion-Exclusion for dummies?

Question

Hi. I'm getting ready for a discrete math final on Wednesday, and of all the topics I don't really "grok", chief among them is the principle of inclusion-exclusion and specifically the derivation of the formula for derangements.

I get it at a high level, but I was hoping maybe someone out there with a gift for explaining mathematical concepts well might have a go at trying to simplify the explanation for my benefit.

I'm aware of http://en.wikipedia.org/wiki/Derangement, but it's a little too formal for my taste. A link to a friendlier discussion would be great, however.

I would really appreciate it if people would avoid posting flippant answers like "I don't know, look it up" or "you must be deranged to ask such a question". There are lots of other questions out there you can use to get your 2 points.

Thanks in advance!

Answer 1

The principle of inclusion-exclusion (PIE) is to overcount what you want to count and then subtracting what was overcounted. The advantage of doing this is that it might be easier to do the overcounting and to count what was overcounted, than to directly count what you need to count. Here is a question that illustrates the cleverness of this principle.

Suppose you are given the six letters A, B, C, D, E, and F. How many 3 letter "words" can you make using these letters, repetition allowed, that have at least one E?
The brute force method would involve drawing some sort of tree diagram or complicated case work since no simple multiplication will take into account the possible place of the E in the word and the number of E's in the word.
The solution applying PIE is much simpler. It is easy to count the total number of words you can make, with no restriction. It is simply 6^3=216, since there are six choices for the first letter, six for the second, and six for the third. However, you overcounted by exactly the words that have no E's, so subtract the number of words without E's. This is also easy to calculate; since you only have 5 choices for the first, second and third letters, there are 5^3=125 words that do not have E. Then the number of words that have at least one E is 216-125=91.

A derangement is a permutation that leaves no element fixed. An example: If your ordered 4-tuple is (1,2,3,4), one derangement would be (2,3,4,1).
So the question is how many derangements of a set with 4 elements are there? We will use PIE.
First, we ask, "How many permutations of 4 elements are there?", since the derangements are permutations with a special restriction. This answer is easy; it's 4!=4 x 3 x 2 x 1 = 24, since there are 4 choices for the first element, 3 for the second, 2 for the third and 1 for the last.
By how much did we overcount? We counted permutations that fixes elements; one such permutation is (1,4,3,2), since the position of 1 does not change. To count this number, we apply PIE.
There are several cases. Suppose we want to count the permutations that fix 1. Since 1 is fixed, there are 3! permutations of the remaining 3 elements. The same is true if we were to fix 2 or 3 or 4. So we subtract 4 x 3!=24.
However, you probably noticed that some permutations were subtracted twice, specifically the permutations that fix more than one element. So we need to apply PIE again to count the number of permutations that fix two elements.
Pick two elements to fix. There are 4C2 ways to do this. Then there are 2! permutations of the remaining elements. We add (4C2)(2!)=12.
The next step is to subtract the permutations that were overcounted again. These are the permutations that leave three elements fixed. There are (4C3)(1!)= 4 of these.
The last step is to add back the permutations that were overcounted yet again. These permutations leave 4 elements fixed, so there is only (4C4)(0!)=1.
The final answer is 4! - 4 x 3! + (4C2)(2!) - (4C3)(1!) + 1 = 9.
This can be generalized to n-tuples: n! - (nC1)((n-1)!) + (nC2)((n-2)!) - (nC3)((n-3)!)+ ..., which through some algebraic manipulation becomes the formula you see on MathWorld.

Answer 2

My internet connections playing up, so I can't see what that wiki page says. Hopefully my answer will come out to be the same :)

PIE (principle of inclusion/exclusion in its common abbreviation) is probably easiest to see on a Venn diagram. Lets say you have a whole bunch of overlapping events, and want to find out the total area covered by them.
We add up all the individual areas. Have we overcounted? Yes - every area where two or more events overlap is counted multiple times - once for every overlap of two events.
So, now lets look at pairs of events, add up all those intersections, and subtract that off the total. However, now we have gone too small - whenever *3 or more* events overlap, we have subtracted off too much. So we add on intersections of 3 events, etc etc.

Anyway, I think you gave the impression you got that (generally), so lets go on to derangements. Or, the opposite - lets count how many permutations of {1,2,..,n} are *not* a derangement.
Well, since its not a derangement, there must be some number i that goes in the ith position. There are (n-1)! ways of putting 1 in the first position (ie, arranging the other n-1 numbers), (n-1)! ways of putting 2 in the second position, etc. Adding those all up gives n(n-1)!, which I will write as nC1 (n-1)!, since n = nC1 (n choose 1).
Now, every time 2 or more numbers are in the right position, we have overcounted.
So, now lets consider each pair of numbers. 1 and 2 occur in the right positions in (n-2)! ways, 1 and 3 occur in (n-2)! ways, ..., n-1 and n occur in (n-2)! ways. There were nC2 possible pairs, so we subtract nC2 (n-2)!.
As before, we have subtracted off too much when three numbers were in the correct position. So we add nC3 (n-3)!, then subtract nC4 (n-4)!.. etc.
So the final number of non-derangements will be:
nC1 (n-1)! - nC2 (n-2)! + nC3 (n-3)! - ...
So we subtract that from n! to find the number of derangements, and I'll write that as nC0 n! to be consistent:
nC0 n! - nC1 (n-1)! + nC2 (n-2)! - ...

Now, we could actually simplify that using definition of nCk:
nCk (n-k)! = n! / (k!(n-k)!) * (n-k)! = n!/k!.

So we actually get n!/0! - n!/1! + n!/2! - ...

Then I think theres actually a cool trick where you notice that 1/0! - 1/1! + 1/2! - 1/3! + ... is just a series for 1/e, so you get [n!/e]. But thats besides the point.

Is that what they get? Hope it helps, anyway.

Answer 3

Discrete Mathematics For Dummies

Answer 4

The "Dummies.." sequence has been wildly effective. I celebrate with them, yet i'm having a difficult time with "Gravitational Lens outcomes for Dummies". heavily, there's no longer one concern those books do not cover, yet one stands proud in my thoughts as thoroughly unnecessary. i change into status in the marketplace checkout line and placed proudly displayed through the cashier: "being pregnant for Dummies". that is the 'Dummies' area I that disturbs me the most...