I know this part but my main doubt was that if there were two repetitions, AA II then how to fix the XX problem.
Do we use Inclusion-Exclusion there also like when we fix A and move another A to it's place there is a chance that the other I deranges also, so in the three cases we count the times I deranges also so should we exclude that?
O.K. I'll have a go. But I'm not going to use 11 letter with 3 pairs of repeats. We'll get lost in the details. I'll use a simpler example (which will be bad enough) and hopefully you can extend the argument.
I don't know what your background is in set theory, but understanding the logic in counting derangements is based on counting the # elements in the union of sets.
U = "union"
n = # of elements in a set
AB = the set "A intersect B"
n(A U B U C) = n(A) + n(B) + n(C) - n(AB) - n(AC) - n(BC) +n(ABC)
To count the # of elements in A U B U C we first add up the # of elements in each of the 3 sets. But this counts the # elements in each pair of intersections twice so we subtract them to only count them once. But by doing the 3 subtractions we have subtracted the # of elements in the intersection of all 3 so we need to add it back on so as to count them only once.
So a derangement is an arrangement of a set of n elements for which none of the elements is in the correct position. For example, take the set 1,2,3. there are 3! arrangements. The arrangement 3,1,2 is called a derangement since none of the elements is in the original position. On the other hand, 3,2,1 is an arrangement but not a derangement since the 2 is in the original position.
Consider a set with n elements. We have to count # of derangements indirectly. Start with the the total # of arrangements, n!, and subtract the # of arrangements where at least one is in the correct position.
# of arrangements in which at least one is in the correct position is done by cases.
notation: x C y means "x choose y"
1) Place exactly 1 letter in the correct position.
n C 1 ways to pick which letter is in the correct position and
(n-1)! ways to arrange the remaining n-1 letters
(n C 1)(n-1)!
2) Place exactly 2 letters in the correct position
n C 2 ways to pick the 2 letters that are in the correct position and
(n-2)! ways to arrange the remaining n-2 letters.
(n C 2)(n-2)!
Now here is the kicker. The arrangements in (2) have already been counted in (1) so we have to subtract to only count them once.
3) Place exactly 3 letters in the correct position
n C 3 ways to pick the 3 letters that are in the correct position and
(n-3)! ways to arrange the remaining n-3 letters.
(n C 3)(n-3)!
Now for the next kicker. All the arrangements in (3) were counted in both (1) and (2) so we have to add them back so they count only once.
Rinse and repeat for as many times as you need.
(n C 1)(n!) - (n C 2)(n-2)! + (n C 3)(n-3)! - (n C 4)(n-4)! + .......
Note that if n is even the last term is negative and if n is odd then we end in a positive term
So finally we subtract this sum from n!
===============================
EXAM - 4 letters - no repeats.
Total # of arrangements = 4! = 24
(4 C 1)3! - (4 C 2)2! + (4C3)1! - (4 C 4)0!
= 24 - 12 + 4 - 1
=15
# of derangements = 25 - 15 = 9
================================
EXXAM - 5 letters - 1 letter repeated 2 times.
1) Assume 5 letters - no repeats
5! = 120
(5 C 1)4! - (5 C 2)3! + (5 C 3)2! - (5 C 4)1! + (5 C 5)0!
= 120 - 60 + 20 - 5 + 1
=76
120 - 76 = 44 derangements
Now we need to fix the XX problem - 3 cases
1) swap the 2 X's
(3 C 1)2! - (3C2)1! + (3 C 3)0!
= 6 - 3 + 1
= 4
and 3! - 4 = 6 - 4 = 2
2) 1st X goes to 2nd X, 2nd X goes somewhere else
(4 C 1)3! - (4 C 2)2! + (4 C 3)1! - (4 C 4)0!
=24 - 12 + 4 -1
=15
and 4! - 15 = 24 - 15 = 9
3) 2nd X goes to 1st X, 1st X goes somewhere else
same as (2) = 9
44 - 2 - 9 - 9 = 24
But we have one more step: Each one is counted twice.
Do you have a final answer so I can check? - before I spend the next 2-3 hours re-learning derangements. The 2 A's, 2 N's and 2 I's make this a hell of a mess.
Do you know about this?
d(1) = 0 , d(2) = 1 and for n>=2
d(n+1) = n[ d(n) + d(n-1) ]
I know this part but my main doubt was that if there were two repetitions, AA II then how to fix the XX problem.
Do we use Inclusion-Exclusion there also like when we fix A and move another A to it's place there is a chance that the other I deranges also, so in the three cases we count the times I deranges also so should we exclude that?
O.K. I'll have a go. But I'm not going to use 11 letter with 3 pairs of repeats. We'll get lost in the details. I'll use a simpler example (which will be bad enough) and hopefully you can extend the argument.
I don't know what your background is in set theory, but understanding the logic in counting derangements is based on counting the # elements in the union of sets.
U = "union"
n = # of elements in a set
AB = the set "A intersect B"
n(A U B U C) = n(A) + n(B) + n(C) - n(AB) - n(AC) - n(BC) +n(ABC)
To count the # of elements in A U B U C we first add up the # of elements in each of the 3 sets. But this counts the # elements in each pair of intersections twice so we subtract them to only count them once. But by doing the 3 subtractions we have subtracted the # of elements in the intersection of all 3 so we need to add it back on so as to count them only once.
So a derangement is an arrangement of a set of n elements for which none of the elements is in the correct position. For example, take the set 1,2,3. there are 3! arrangements. The arrangement 3,1,2 is called a derangement since none of the elements is in the original position. On the other hand, 3,2,1 is an arrangement but not a derangement since the 2 is in the original position.
Consider a set with n elements. We have to count # of derangements indirectly. Start with the the total # of arrangements, n!, and subtract the # of arrangements where at least one is in the correct position.
# of arrangements in which at least one is in the correct position is done by cases.
notation: x C y means "x choose y"
1) Place exactly 1 letter in the correct position.
n C 1 ways to pick which letter is in the correct position and
(n-1)! ways to arrange the remaining n-1 letters
(n C 1)(n-1)!
2) Place exactly 2 letters in the correct position
n C 2 ways to pick the 2 letters that are in the correct position and
(n-2)! ways to arrange the remaining n-2 letters.
(n C 2)(n-2)!
Now here is the kicker. The arrangements in (2) have already been counted in (1) so we have to subtract to only count them once.
3) Place exactly 3 letters in the correct position
n C 3 ways to pick the 3 letters that are in the correct position and
(n-3)! ways to arrange the remaining n-3 letters.
(n C 3)(n-3)!
Now for the next kicker. All the arrangements in (3) were counted in both (1) and (2) so we have to add them back so they count only once.
Rinse and repeat for as many times as you need.
(n C 1)(n!) - (n C 2)(n-2)! + (n C 3)(n-3)! - (n C 4)(n-4)! + .......
Note that if n is even the last term is negative and if n is odd then we end in a positive term
So finally we subtract this sum from n!
===============================
EXAM - 4 letters - no repeats.
Total # of arrangements = 4! = 24
(4 C 1)3! - (4 C 2)2! + (4C3)1! - (4 C 4)0!
= 24 - 12 + 4 - 1
=15
# of derangements = 25 - 15 = 9
================================
EXXAM - 5 letters - 1 letter repeated 2 times.
1) Assume 5 letters - no repeats
5! = 120
(5 C 1)4! - (5 C 2)3! + (5 C 3)2! - (5 C 4)1! + (5 C 5)0!
= 120 - 60 + 20 - 5 + 1
=76
120 - 76 = 44 derangements
Now we need to fix the XX problem - 3 cases
1) swap the 2 X's
(3 C 1)2! - (3C2)1! + (3 C 3)0!
= 6 - 3 + 1
= 4
and 3! - 4 = 6 - 4 = 2
2) 1st X goes to 2nd X, 2nd X goes somewhere else
(4 C 1)3! - (4 C 2)2! + (4 C 3)1! - (4 C 4)0!
=24 - 12 + 4 -1
=15
and 4! - 15 = 24 - 15 = 9
3) 2nd X goes to 1st X, 1st X goes somewhere else
same as (2) = 9
44 - 2 - 9 - 9 = 24
But we have one more step: Each one is counted twice.
24/2 = 12
AMEXX AEMXX MAEXX MEAXX XEAMX XEMXA XAEMX XAMEX XAMXE XMAEX
XMAXE XMEXA - 12 as promised
You have to fix the XX problem 3 times (each one 3 cases) - AA,NN,II for your 11 letters. Good luck.
Do you have a final answer so I can check? - before I spend the next 2-3 hours re-learning derangements. The 2 A's, 2 N's and 2 I's make this a hell of a mess.