2
$\begingroup$

There are 4 letters with their 4 corresponding envelopes, along with 2 extra envelopes not bearing any letter. In how many ways can these letters be deranged? If A) the two extra envelopes are identical. B) the two extra envelopes are distinct.

I was able to solve part (B) using inclusion-exclusion, but my attempt for part (A) yielded wrong result.

My attempt:

Case 1: when no extra envelope is used then number ways is $D_4$.

Case 2: when 1 of the identical extra envelope is used then number of ways is $D_5$. (By assuming dummy letter for the extra envelope.)

Case 3: when both extra envelopes are used, then number of ways is same as : $ 4C2 •( 1+ 2C1•2C1 + 2!) $

EXPLANATION of case 3 : choosing 4 letters of the 2 identical envelopes (let A and B) and placing them there, then either exchanging the other two letters (let C and D) of their envelopes, Or choosing 1 out of C and D and placing them in one out of A's or B's envelope, Or placing C or D in A's or B's envelope in 2 ways.

Apparently, my answer is wrong. Can you help?

$\endgroup$
4
  • $\begingroup$ "Apparently my answer is wrong" What answer are you told is correct? That can help save time. $\endgroup$
    – JMoravitz
    Jun 3, 2020 at 15:00
  • $\begingroup$ @JMoravitz, The answer given is 143 ways, but my answer is 95. $\endgroup$
    – ba-13
    Jun 3, 2020 at 15:04
  • $\begingroup$ I can not see anything wrong with your logic. I suspect this to be a mistake on their part... I might write a quick script to manually check if I have time during lunch $\endgroup$
    – JMoravitz
    Jun 3, 2020 at 15:11
  • $\begingroup$ @JMoravitz, thank you. I will see if there is any solution given or not, and then pinpoint the mistake. $\endgroup$
    – ba-13
    Jun 3, 2020 at 15:23

1 Answer 1

1
$\begingroup$

Given my interpretation of the problem, your answer is correct and I agree with your logic and would have done it in almost the same way (opting to use inclusion instead for case 3)

This is verified by the following quick and dirty javascript implementation:

permute([1,2,3,4,5,6]) //using answer from https://stackoverflow.com/questions/9960908/permutations-in-javascript
count = 0;
for(k=0; k<720; k++){
   curperm = permArr[k]
   if (curperm[0]!= 1 && curperm[1]!= 2 && curperm[2]!=3 && 
       curperm[3]!= 4 && curperm[4]<curperm[5] && curperm.indexOf(5)<curperm.indexOf(6)){
           console.log(curperm);count++
   }
}
console.log(count)

The idea behind the code being that to account for the two blank envelopes being indistinguishable we can account for this by ensuring the labels of the contents being written in increasing order, and the two dummy blank letters being indistinguishable by their positions occurring in increasing order. Otherwise, the fact that it is a derangement is in checking the positions of the first four letters not being in their respective original envelopes.

It is, as mentioned, a bit dirty... but it confirms an answer of $95$. The list of valid derangements begins:

[2, 1, 4, 3, 5, 6]
[2, 1, 4, 5, 3, 6]
[2, 1, 5, 3, 4, 6]
[2, 1, 5, 6, 3, 4]
[2, 3, 1, 5, 4, 6]
[2, 3, 4, 1, 5, 6]
[2, 3, 4, 5, 1, 6]
[2, 3, 5, 1, 4, 6]
[2, 3, 5, 6, 1, 4]
[2, 4, 1, 3, 5, 6]
[2, 4, 1, 5, 3, 6]
[2, 4, 5, 1, 3, 6]
[2, 4, 5, 3, 1, 6]
...

keeping in mind that here we are treating $5$ and $6$ as identical and the last two positions as indistinguishable

$\endgroup$
1
  • $\begingroup$ I asked my teacher and found the solution to contain a '$4C2•2C1$' instead in the 3rd case. Maybe the Answer was given wrong. $\endgroup$
    – ba-13
    Jun 3, 2020 at 15:38

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .