0
$\begingroup$

Original question (Too long for title): Number of ways to arrange the letters in CACHES so that the letter C is not in the first or third position and none of the letters A, H, E, S is in its original position

The given answer is 84.

My approach: I think it should be equal to the number of derangements of a set of size 6 minus the number of derangements where the 3rd C is swapped to the 1st position or where the 3rd C is swapped to the 1st position, or

$d_6$ - N(derangements where $C_1$ is in 3rd position) - N(derangements $C_3$ is in 1st position) + N(derangements where $C_1$ is in 3rd position and $C_3$ is in 1st position)

= 265 - $d_5$ - $d_5$ + $d_4$ = 265 - 2*44 + 9 = 186

Can someone point out what is wrong with my method, and hopefully tell me how it can be solved this way.

$\endgroup$
2
$\begingroup$

The issue is that you are assuming that N(derangements where $C_1$ is in third position) is equivalent to $d_5$. Same for $C_3$ and first position.

To understand this, let's represent derangements in a different way. Set up a grid (I'm using matrices) in the following way \begin{bmatrix} &A&B&C&D&E&F\\ A &1&0&0&0&0&0\\ B &0&1&0&0&0&0\\ C &0&0&1&0&0&0\\ D &0&0&0&1&0&0\\ E &0&0&0&0&1&0\\ F &0&0&0&0&0&1\\ \end{bmatrix} Now we can understand the number of derangements of ABCDEF as the number of ways to choose 6 different entries that are 0, one from every row and column (excluding the row and column with letters of course).

This grid is a representation of your problem. \begin{bmatrix} \ &C&A&C&H&E&S \\ C&1&0&1&0&0&0 \\ A&0&1&0&0&0&0 \\ C&1&0&1&0&0&0 \\ H&0&0&0&1&0&0 \\ E&0&0&0&0&1&0 \\ S&0&0&0&0&0&1 \end{bmatrix}

You tried to solve it by ignoring that the Cs were the same and approaching it like a normal derangement. \begin{bmatrix} \ &C_1&A_2&C_3&H_4&E_5&S_6 \\ C_1&1&0&0&0&0&0 \\ A_2&0&1&0&0&0&0 \\ C_3&0&0&1&0&0&0 \\ H_4&0&0&0&1&0&0 \\ E_5&0&0&0&0&1&0 \\ S_6&0&0&0&0&0&1 \end{bmatrix}

Then you subtracted the number of ways that $C_1$ was in the third slot (i.e. "remove" the third column or slot as well as the first row). $$\begin{bmatrix} \ &C_1&A_2& &H_4&E_5&S_6 \\ & & & & & & \\ A_2&0&1& &0&0&0 \\ C_3&0&0& &0&0&0 \\ H_4&0&0& &1&0&0 \\ E_5&0&0& &0&1&0 \\ S_6&0&0& &0&0&1 \end{bmatrix} => \begin{bmatrix} \ &C_1&A_2&H_4&E_5&S_6 \\ A_2&0&1&0&0&0 \\ C_3&0&0&0&0&0 \\ H_4&0&0&1&0&0 \\ E_5&0&0&0&1&0 \\ S_6&0&0&0&0&1 \end{bmatrix}$$

Same for $C_3$ and the first slot. $$\begin{bmatrix} \ & &A_2&C_3&H_4&E_5&S_6 \\ C_1& &0&0&0&0&0 \\ A_2& &1&0&0&0&0 \\ & & & & & & \\ H_4& &0&0&1&0&0 \\ E_5& &0&0&0&1&0 \\ S_6& &0&0&0&0&1 \end{bmatrix} => \begin{bmatrix} \ &A_2&C_3&H_4&E_5&S_6 \\ C_1&0&0&0&0&0 \\ A_2&1&0&0&0&0 \\ H_4&0&0&1&0&0 \\ E_5&0&0&0&1&0 \\ S_6&0&0&0&0&1 \end{bmatrix}$$

And finally, because you subtracted too much, you added in the extra case where both of the Cs were switched.

$$\begin{bmatrix} \ & &A_2& &H_4&E_5&S_6 \\ & & & & & & \\ A_2& &1& &0&0&0 \\ & & & & & & \\ H_4& &0& &1&0&0 \\ E_5& &0& &0&1&0 \\ S_6& &0& &0&0&1 \end{bmatrix} => \begin{bmatrix} \ &A_2&H_4&E_5&S_6 \\ A_2&1&0&0&0 \\ H_4&0&1&0&0 \\ E_5&0&0&1&0 \\ S_6&0&0&0&1 \end{bmatrix}$$

However, looking at the second (or third) grid: \begin{bmatrix} \ &C_1&A_2&H_4&E_5&S_6 \\ A_2&0&1&0&0&0 \\ C_3&0&0&0&0&0 \\ H_4&0&0&1&0&0 \\ E_5&0&0&0&1&0 \\ S_6&0&0&0&0&1 \end{bmatrix} you can clearly see that this is not a representation of a derangement.

Does that make sense? I couldn't think of another way to explain it.

Edit:

Here's a much better way to explain where you went wrong then how I did originally.

The problem is you are assuming that $N(\text{derangements where }C_1\text{ is fixed in the third position}) = d_5$. This is wrong because the position of $C_3$ is independent of the derangements where $C_1$ is in third position, i.e. $C_3$ can go into any of the other five positions and is therefore not a derangement. Same vice versa.

However, if we make a derangement by fixing $C_1$ in the third position and considering the first position to be the original position of $C_3$, then this is equivalent to a derangement of a set of size 5. Again, same vice versa. As for the instance where $C_1$ and $C_3$ are switched, it is easy to show that this is equivalent to a derangement of a set of size 4 - as you have already done. So in conclusion:

$$N(\text{"derangements" of CACHES}) = N(\text{derangements of }C_1A_2C_3H_3E_4S_5) - N(\text{derangements where $C_3$ is fixed and $C_1$ is considered to be originally in third position}) - N(\text{derangements where $C_1$ is fixed and $C_3$ is considered to be originally in first position}) - N(\text{derangements where $C_1$ and $C_3$ are fixed in switched positions}) = d_6 - d_5 - d_5 - d_4 = 168$$


However, this is different from your answer of 84. So either 84 is the wrong answer or the question is not described clearly. I wrote a program (in Python) to calculate the number of derangements of CACHES:


from itertools import product

# Get all possible permutations of six integers that are 0-5
# l = [(0,0,0,0,0,0), (0,0,0,0,0,1), (0,0,0,0,0,2), ...]
l = [x for x in product([0, 1, 2, 3, 4, 5], repeat=6)]
# Filter it down to unique arrangements of the integers 0-5
# l2 = [(0,1,2,3,4,5), (0,1,2,3,5,4), ...]
l2 = [x for x in l if sorted(list(set(x)))==sorted(x)]

s = 'CACHES'
# Create a list of all permutations of CACHES
y = [s[a]+s[b]+s[c]+s[d]+s[e]+s[f] for a,b,c,d,e,f in l2]

# Remove permutations with first letter being C
y1 = [x for x in y if x[0]!='C']

# Remove permutations with first letter being A
y2 = [x for x in y1 if x[1]!='A']

# Etc.
y3 = [x for x in y2 if x[2]!='C']
y4 = [x for x in y3 if x[3]!='H']
y5 = [x for x in y4 if x[4]!='E']
y6 = [x for x in y5 if x[5]!='S']

print(len(y6))
# Prints out "168"

$\endgroup$
1
$\begingroup$

This is equivalent to counting the number of functions $f:\{1,2,3,4,5,6\} \rightarrow \{1,2,3,4,5,6\}$ such that $f(1) \neq 1, 3$, $f(3) \neq 1,3$, $f(i) \neq i$, $i = 2,4,5,6$. The $(1,3)$ pair must be mapped to two among $2,4,5,6$. This can be done in 6 ways. Suppose that $1 \rightarrow 2, 3 \rightarrow 4$. Then we have to map $5, 6, 2, 4$ to $5,6,1,3$. This, by inclusion exclusion principle is $$4! - 3! - 3! + 2! = 14$$ The same is the case when we map $1,3$ to any other pair among $2,4,5,6$. Thus the total number of ways is $14 \times 6 = 84$.

$\endgroup$
0
$\begingroup$

The difference between the answer 168 from Noah May and the 84 apparently given with the problem is just a factor of 2: In Noah's calculation the two C's are still considered different and a swap between them produces a different solution, while there is no such difference between the C's in the problem. In other words, each of the 84 solutions of the problem, like

$$\mathrm{ACSCHE}$$

maps two 2 solutions in Noah's solution:

$$\mathrm{AC_1SC_3HE\space and\space AC_3SC_1HE} $$

$\endgroup$

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.