Use inclusion/exclusion to find the number of derangements of each of the following strings.

Question

a) aabcd (already answered)

b) aabbcc

There is a problem exactly like the one I asked, however I am still stuck and still need help. Here is my attempt

Let A denotes where aa occurs, B denotes where bb occurs, C denotes where cc occurs, and |U|=$\frac{6!}{2^3}$. Then $|A\cup B\cup C|=|A|+|B|+|C|-(|AB|+|AC|+|BC|)+|ABC|$.

For |A|+|B|+|C| glue aa together for |A|, bb for |B| and cc for |C|

|A|: $\frac{5!}{2^2}$ |B|: $\frac{5!}{2^2}$ |C|: $\frac{5!}{2^2}$ $\implies$ |A|+|B|+|C|=$3\left(\frac{5!}{2^2}\right)$

For |AB|+|AC|+|BC|=$3\left(\frac{4!}{2}\right)$

For |ABC|= 3!

So |U|-$|A\cup B\cup C| = \frac{6!}{2^3}-\left[\frac{5!}{2^2}-3\left(\frac{4!}{2}\right)+3!\right] = 30$

Now thanks to the people who already answered this we know that the actual answer is 10.

As you all can see I am doing something wrong, but I not sure what. By using the Inclusion-Exclusion Principle please help me figure out how I need to get the correct answer.

Answer 1

Let's work out the first example (we'll use common letters for convenience):

$aabcd$

First letter $a$ needs to go to position $3,4$ or $5$ so $3$ choices

Second letter $a$ now should have the same $3$ choices but the first letter $a$ already took a spot, so $2$ choices.

Those first two $a$'s don't generate $3*2$ combinations but only $3$, of the form $\cdot \cdot aa\cdot ,\cdot\cdot a\cdot a,\cdot\cdot\cdot aa$

Now for the last three letters we can work them all in one pack : if the first two $a$ didn't take their place, then they have only $2$ choices, if not, they have $3$ choices. There can only be one of the three initial letters $cde$ so that none of the two $a$ moved to their spot, so one letter out of $cde$ has $2$ choices, and the two left have each $3$ choices. Thanks to Platty you also need to take into consideration that each time you place one of those three letters you take away a spot for the remaining letters so they generate $2*2*1$ combinations.

So finally we got the number of possible derrangement : $3*2*2*1=12$

For the second string $aabbcc$ the number of derangement is $10$.

Answer 2

I'll help you with the first one. The second is similar.To make stuff easier, I'll write the string as $\alpha_1\alpha_2\beta\gamma\delta$.

Note that the number of derangements for the string is $D_5$. However, in ${\frac{1}{4}}^{th}$ of those we have $\alpha_1$ in the second position. The same holds true when $\alpha_2$ is in the first position. We thus get, $D_5 - \frac{2}{4}D_5$. We have however, over-subtracted the case when $\alpha_2$ is in the first position and $\alpha_1$ is in the first. This happens in ${\frac{D_3}{D_5}}^{th}$ of the cases (Fix the positions for the first two letters; the rest can be deranged in $D_3$ ways).

The final answer is thus, $$D_5 - \frac{2}{4}D_5 + \frac{D_3}{D_5}D_5$$

Since the two $\alpha$s are indistinguishable, the final answer is $\frac{24}{2} = 12$