1

All letters of the word ABRACADABRA will be arranged in a row if C, R, and D are not to be together. Find how many ways are possible.

My attempt

  • number of letter A = 5
  • number of letter B = 2
  • number of letter C = 1
  • number of letter D = 1
  • number of letter R = 2

$$ \frac{11!}{5!2!2!}-\frac{8!}{5!2!}\times\frac{4!}{2!}=81144 $$

Combinatorical argumentations are given as follows:

  • Non restricted ways are $\frac{11!}{5!2!2!}$.
  • Eight groups A,A,A,A,A,B,B,P where P is a placeholder for C,D,R,R to be together. So this leads to $\frac{8!}{5!2!}\times\frac{4!}{2!}$.
  • The required answer is the difference between these two values mentioned above.

According to the answer key (I will tell you later), it is wrong!

What is the correct solution?

Friendly Ghost
  • 267

1 Answers1

1

By the inclusion-exclusion principle, the number of permutations of the word $ABRACADABRA$ such that they do not contain any substring of the form $CDR$, $CRD$, $DCR$, $DRC$, $RCD$, $RDC$ should be $$\frac{1}{2}\left(\frac{11!}{5!2!}-2\cdot 3!\cdot \frac{9!}{5!2!}+4\cdot \frac{8!}{5!2!}\right)=74424.$$ We first consider the two $R$s as two different letters, say $R_1$ and $R_2$, then we divide the result by $2$.

Edit: I found the same question HERE, where the suggested answer is $$\frac{1}{2}\left(\frac{11!}{5!2!}-3!\cdot \frac{9!}{5!2!}\right)=78624$$ but I think that the result and the reasoning is not correct due to overcounting.

Robert Z
  • 145,942