1
$\begingroup$

$9$ letters and $9$ envelopes are denoted by $\{A, B, C, D, \ldots, I\}$ and $\{a, b, c, \ldots, i\}$ respectively. To find the number of ways so that no letter goes into right envelope but given letters $A$ and $B$ would go to envelopes $b$ and $f$ respectively. Can we generalise the result for other such questions?

My method for solving for the case when letter $A$ went to $b$ and other letters also went to wrong envelope was that- since $A$ has to go to wrong envelope, it must have went to any of $\{b, c, \ldots, i\}$. So there are $8$ such envelopes, each case equally probable. Since it is given that letter $A$ has went to $b$ so there are $D_9$/$(9-1)$ ways. Generalising, given one such constraint, the formula will be $D_n/(n-1)$. I could not create any such formula for two or three constraints.

Since the case given is not symmetric, that is, it can't be partitioned into any cases, I think this requires some other technique . I did it by just counting and couldn't have generalised it :).

Please give me a proper answer considering there are two such constraints.

$\endgroup$
  • 1
    $\begingroup$ Please edit your question to show what you have attempted and to explain what difficulties you are having, if any. This MathJax tutorial explains how to typeset mathematics on this site. $\endgroup$ – N. F. Taussig Sep 25 '18 at 18:15
  • $\begingroup$ If the only constraint were that $A$ went to $b$, there are two cases. One is a swap in which $B$ goes to $a$, in which case you have a derangement on the remaining seven letters. The other case is that $B$ does not go $a$, in which case you have a derangement on the remaining eight letters since each letter has one envelope to which it cannot go. $\endgroup$ – N. F. Taussig Sep 26 '18 at 7:47
1
$\begingroup$

Let's start with the preliminary question:

In how many ways can the nine letters $\{A, B, C, D, E, F, G, H, I\}$ be placed in the nine envelopes $\{a, b, c, d, e, f, g, h, i\}$ so that letter $A$ is placed in envelope $b$ and no letter is placed in the correct envelope?

If letter $A$ is placed in envelope $b$, there are two possibilities:

  1. Letter $B$ is placed in envelope $a$. Then each of the seven letters not already placed has one prohibited envelope, namely its own envelope. Thus, there must be a derangement on the remaining seven envelopes. Hence, there are $D_7$ such cases.
  2. Letter $B$ is not placed in envelope $a$. Then each of the eight letters not already placed has one prohibited envelope, its own envelope for each letter other than letter $B$ and envelope $a$ for letter $B$. Hence, there must be a derangement on the eight letters not already placed, so there are $D_8$ such cases.

Since these two cases are mutually exclusive, the number of ways the nine letters can be placed in the nine envelopes so that letter $A$ is placed in envelope $b$ and no letter is placed in the correct envelope is $D_7 + D_8$.

In how many ways can the nine letters $\{A, B, C, D, E, F, G, H, I\}$ be placed in the nine envelopes $\{a, b, c, d, e, f, g, h, i\}$ so that letter $A$ is placed in envelope $b$, letter $B$ is placed in envelope $f$, and no letter is placed in the correct envelope?

Again, there are two possibilities:

  1. Letter $F$ is placed in envelope $a$. Then each of the six letters that has not already been placed has one prohibited envelope, namely its own. Hence, there are $D_6$ such cases.
  2. Letter $F$ is not placed in envelope $a$. Then each of the seven letters that has not already been placed has one prohibited envelope, its own envelope for each letter other than $F$ and envelope $a$ for letter $F$. Hence, there are $D_7$ such cases.

Since these two cases are mutually exclusive and exhaustive, the number of ways the nine letters can be placed if letter $A$ is placed in envelope $b$, letter $B$ is placed in envelope $f$, and no letter is placed in the correct envelope is $D_6 + D_7$.

$\endgroup$
  • 1
    $\begingroup$ Thanks for the solution and explanation. This logic is quite better than mine. Both yields the same answer but this logic is better. $\endgroup$ – user597086 Oct 5 '18 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.