Derangement with constraints

combinatorial-proofscombinatorics

$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.

Best Answer

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$.

Related Question