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.

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.

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?

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.

Don't actually have an answer just want to know the process that goes behind 😅

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

is in the correct position.at least one# of arrangements in whichat least oneis 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 positionn 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 positionn 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 derangementsNow we need to fix the XX problem - 3 cases1) swap the 2 X's

(3 C 1)2! - (3C2)1! + (3 C 3)0!

= 6 - 3 + 1

= 4

and 3! - 4 = 6 - 4 =

22) 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 =

93) 2nd X goes to 1st X, 1st X goes somewhere else

same as (2) =

944 - 2 - 9 - 9 = 24But we have one more step: Each one is counted twice.

24/2 = 12AMEXX 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.

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?

Do you know about this?

d(1) = 0 , d(2) = 1 and for n>=2d(n+1) = n[ d(n) + d(n-1) ]