[Math] Arrangements using the letters of the word BOOKKEEPER with some constraints

permutations

This is my first question here. We are facing difficulty with one permutation question.

We were asked to find the different counts possible using the letters of the word BOOKKEEPER.

This was easy. The answer can be arrived as 10!/(2!*2!*3!) which comes to 151200

We have also done another question to count different counts possible using the letters of the word BOOKKEEPER, but this time with an added condition that E's must not come together in any of the formed words.

We could solve this as well. We used the approach of first arranging the non-'E' letters and then arranging 'E' in the gaps. Answer was arrived correctly as 70560

Now there is one question given to us which is really hard.

The condition was modified and this time 'E's cannot be together. Similarly 'O's also cannot be adjacent.

We do not have any idea on the approach to be used for this. Please help if anyone has already approached a similar situation.

Best Answer

Method 1: We arrange the five letters B, K, K, P, R in a row, then insert the two O's and three E's in that order.

The number of ways we can arrange the five letters B, K, K, P, R in a row is $$\frac{5!}{2!}$$ where we divide by $2!$ since we can permute the two K's within a given arrangement without producing an arrangement distinguishable from that arrangement.

We now have six spaces to fill, four between successive letters and two at the ends of the row. We can either place both O's in one of these six spaces, which can be done in $\binom{6}{1}$ ways, or place them in two different spaces, which can be done in $\binom{6}{2}$ ways.

Case 1: We place both O's in one of the six spaces.

This creates an arrangement with seven letters in which the two O's are adjacent. Since we are not permitted to have two adjacent O's, we must place an E in between the two O's. We now have an arrangement of eight letters, including the sequence OEO. This creates nine spaces, seven between successive letters and two at the ends of the row. Since the E's cannot be adjacent, we must separate them by placing an E in two of the seven spaces that are not adjacent to the E we have placed between the two O's. We can do this in $\binom{7}{2}$ ways. The number of such arrangements is $$\binom{6}{1}\binom{7}{2}$$

Case 2: The two O's are placed in two different spaces.

This creates an arrangement of seven letters in which the O's are not adjacent. We have eight spaces to fill, six between successive letters and two at the ends of the row. To separate the E's, we choose three of these eight spaces in which to insert an E, which can be done in $\binom{8}{3}$ ways. The number of such arrangements is $$\binom{6}{2}\binom{8}{3}$$

Total: Since the two cases are disjoint, the number of arrangements of BOOKKEEPER in which the E's are not adjacent and the O's are not adjacent is $$\frac{5!}{2!}\left[\binom{6}{1}\binom{7}{2} + \binom{6}{2}\binom{8}{3}\right] = 57960$$

Method 2: We use the Inclusion-Exclusion Principle.

There are $$\frac{10!}{2!3!}$$ distinguishable arrangements of the word BOOKKEEPER. From these we must exclude those arrangements in which two O's or two E's are adjacent.

One pair of adjacent identical letters:

Two O's are adjacent: We have nine objects to arrange: B, OO, K, K, E, E, E, P, R. Since the two K's are indistinguishable and the three E's are indistinguishable, they can be arranged in $$\frac{9!}{2!3!}$$ distinguishable ways.

Two E's are adjacent: We have nine objects to arrange: B, O, O, K, K, EE, E, P, R. Since the two O's are indistinguishable and the two K's are indistinguishable, they can be arranged in $$\frac{9!}{2!2!}$$ distinguishable ways.

Two pairs of adjacent identical letters:

Two O's are adjacent and two E's are adjacent: We have eight objects to arrange: B, OO, K, K, EE, E, P, R. Since the two K's are indistinguishable, they can be arranged in $$\frac{8!}{2!}$$ distinguishable ways.

Two pairs of E's are adjacent: We have eight objects to arrange: B, O, O, K, K, EEE, P, R. Since the two K's are indistinguishable and the two O's are indistinguishable, they can be arranged in $$\frac{8!}{2!2!}$$ distinguishable ways.

Three pairs of adjacent identical letters:

Two O's are adjacent and two pairs of E's are adjacent: We have seven objects to arrange: B, OO, K, K, EEE, P, R. Since the two K's are indistinguishable, they can be arranged in $$\frac{7!}{2!}$$ distinguishable ways.

By the Inclusion-Exclusion Principle, the number of permissible arrangements is $$\frac{10!}{2!2!3!} - \frac{9!}{2!3!} - \frac{9!}{2!2!} + \frac{8!}{2!} + \frac{8!}{2!2!} - \frac{7!}{2!} = 57960$$