I have this question that states:
Using Inclusion/exclusion, find the number of derangements of each of the following strings.
A) aabcd
B) aabbcc
I understand inclusion/exclusion I just don't understand how it applies to this type of question.
I would appreciate the help and some clarification on how to go about solving these types of problems.
First we have to understand what a derangement is. Suppose we want to count all the derangements of the set {${1,2,3,4,5}$}. That is, we want to count all the permutations for which all the numbers in the set are in an 'incorrect' position.
For instance, suppose we assign $1$ to the first place, $2$ to the second place, $3$ in third, etc. as above, let's call these the natural positions of the set.
Then, {$3,5,2,1,4$} is a derangement where all numbers are not in the "correct" or "natural" position.
What does this have to do with inclusion-exclusion?
Let $A_i$ be an element denoted by the $i$th position being in it's natural position, namely $i$. Then we seek to count all possibilities where no $A_i$ is in its right position. Hence, we want to count:
$|\overline{A_1} \cap \overline{A_2} \cap ... \cap \overline{A_n}|$
But this equals:
$|\overline{A_1 \cup A_2 \cup ... \cup A_n} | = |A|-|A_1 \cup A_2 \cup ... \cup A_n|$
Where $|A|$ is the number of all permutations of regarding $A_1$,$A_2$,...$A_n$.
Then, as you are familiar with inclusion exclusion principle, this term $|A_1 \cup A_2 \cup ... \cup A_n|$ you know how to expand.
This should be enough to get you started. Be mindful when counting since some of your strings have repeating characters.