0

There are 5 letters A,B,C,D and E. How many permutations are possible of these 5 letters if AB , BC , CD & DC are not allowed ? I am very thankful to you if you solve this problem for me and tell me a proper way to solve it.

Aashish
  • 1
  • What do you mean by "AB, BC, CD, & DC are not allowed"? Do you mean I couldn't have, for instance, DBCEA because BC appears in the permutation? – kccu Apr 29 '19 at 13:50
  • Yes! Exactly.... – Aashish Apr 29 '19 at 13:51
  • 1
    Are you familiar with inclusion-exclusion? – kccu Apr 29 '19 at 13:52
  • Yes, But here my problem is .. I can do the 5! - (to remove all AB, BA Permutation)423! = 48 - (to remove all CD, DC Permutation)423! = 48 + (Intersection (How to solve this?)) – Aashish Apr 29 '19 at 13:58

1 Answers1

0

Let $P$ denote the set of all permutations.

Let $P_1$ denote the set of all permutations that contain $AB$ as substring.

Let $P_2$ denote the set of all permutations that contain $BC$ as substring.

Let $P_3$ denote the set of all permutations that contain $CD$ as substring.

Let $P_4$ denote the set of all permutations that contain $DC$ as substring.

Then to be found is:$$|P|-|P_1\cup P_2\cup P_3\cup P_4|$$

Evidently $|P|=5!=120$ and $|P_1\cup P_2\cup P_3\cup P_4|$ can be found by means of the principle of inclusion/exclusion.

Give that a try.

drhab
  • 151,093
  • How to find intersection of P1, P2, P3, P4 as they can have the common permutation. For Ex: ABCDE. These type of term will be minus two times. – Aashish Apr 29 '19 at 14:17
  • @Aashish The intersection of all of them is empty, as no permutation can contain $CD$ and $DC$. But you will need to find all possible pair-wise and $3$-way intersections as well. For instance, how many permutations contain $AB$ and $CD$? Well we can treat $AB$ as a single unit, and $CD$ as well. We need to arrange these units along with the letter $E$, so there are $3!$ such permutations. You can do similar reasoning for the other intersections. – kccu Apr 29 '19 at 14:19
  • @kccu Still I have the problem with BC my friend. How to deal with it? AB,CD,E 3! + AB,DC,E 3! + How to manage BC here (like this: A, BC,D,E) 4! ?? or I am doing further wrong???? – Aashish Apr 29 '19 at 15:15
  • 1
    The permutation will contain the strings AB and BC if and only if it contains the string ABC. So ABC can be looked at as a single unit, resulting in $|P_1\cap P_2|=3!$. Further a permutation cannot contain both strings BC and DC, and also cannot contain both strings CD and DC. So $|P_2\cap P_4|=0=|P_3\cap P_4|$ – drhab Apr 29 '19 at 16:47