Restricted permutation of ABRACADABRA

3.1k Views Asked by At

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?

1

There are 1 best solutions below

1
On BEST ANSWER

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.