Permutations of “OBSEQUIOUSNESS” when Q and U must be together?

126 Views Asked by At

My attempt -

There are O-2 , B -1 , S -4 ,E -2 , Q-1 , U -2 , I - 1 N -1.

So 14 letters.

Now if I take QU as a single letter , there are 13 letters . So the answer is $$\frac{13!}{(2!)(2!)(4!)}\times \frac{2!}{2!}$$

Am I correct?

Since there are two U s in the word , can we have another answer?

If there is no restriction of the order of Q,U , will my answer change ?

I know there are possibilities such as QU , UQ and UQU ... !

2

There are 2 best solutions below

4
On

Number of arrangements where "QU" doesn't come together

You will need to count the total number of arrangements for the word "OBSEQUIOUSNESS" with no restrictions, which would be $$\frac{14!}{2!\times2!\times 2!\times4!}$$

Number of arrangements where "UQ" are together. By taking them as one unit, we then will have $$\frac{13!}{2!\times2!\times4!}$$

Number of arrangements where "QU" are together. By taking them as one unit, we then will have $$\frac{13!}{2!\times2!\times4!}$$

Number of arrangements where "UQU" are together is $$\frac{12!}{2!\times2!\times4!}$$

Total number of arrangements where no "Q" and "U" are not next to each other is $$\frac{14!}{2!\times2!\times 2!\times4!} - ( \frac{13!}{2!\times2!\times4!} + \frac{13!}{2!\times2!\times4!} - \frac{12!}{2!\times2!\times4!} )$$


Update/Edit:

Number of arrangements where "QU" come together:

Will update soon with a correct answer

0
On

As you observed, the word OBSEQUIOUSNESS can be viewed as the multiset $$\{2 \cdot O, 1 \cdot B, 4 \cdot S, 2 \cdot E, 1 \cdot Q, 2 \cdot U, 1 \cdot I, 1 \cdot N\}$$

The number of distinguishable permutations of the letters of the fourteen letters of the word OBSEQUIOUSNESS is \begin{align*} \binom{14}{2}\binom{12}{1}\binom{11}{4}\binom{7}{2}\binom{5}{1}\binom{4}{2}\binom{2}{1}\binom{1}{1}& = \frac{14}{2!12!} \cdot \frac{12!}{1!11!} \cdot \frac{11!}{4!7!} \cdot \frac{7!}{2!5!} \cdot \frac{5!}{1!4!} \cdot \frac{4!}{2!2!} \cdot \frac{2!}{1!1!} \cdot \frac{1!}{1!0!}\\ & = \frac{14}{2!1!4!2!1!2!1!1!} \end{align*} where we successively choose two of the fourteen positions for the Os, one of the remaining twelve positions for the B, four of the remaining eleven positions for the Ss, two of the remaining seven positions for the Es, one of the remaining five positions for the Q, two of the remaining four positions for the U, one of the remaining two positions for the I, and the final position for the N.

In how many permutations of the letters of the word OBSEQUIOUSNESS are the letters Q and U together?

Method 1: We use the Inclusion-Exclusion Principle, as Barry Cipra suggested in the comments.

If the letters Q and U must be together, then a permutation of OBSEQUIOUSNESS contains the subsequence QU or the subsequence UQ. If it contains QU, then we have a permutation of the $13$-element multiset $$\{2 \cdot O, 1 \cdot B, 4 \cdot S, 2 \cdot E, 1 \cdot QU, 1 \cdot U, 1 \cdot I, 1 \cdot N\}$$ of which there are $$\binom{13}{2}\binom{11}{1}\binom{10}{4}\binom{6}{2}\binom{4}{1}\binom{3}{1}\binom{2}{1}\binom{1}{1} = \frac{13!}{2!1!4!2!1!1!1!1!}$$ distinguishable permutations, as you found. If it contains UQ, then we have a permutation of the $13$-element multiset $$\{2 \cdot O, 1 \cdot B, 4 \cdot S, 2 \cdot E, 1 \cdot UQ, 1 \cdot U, 1 \cdot I, 1 \cdot N\}$$ of which there are also $$\binom{13}{2}\binom{11}{1}\binom{10}{4}\binom{6}{2}\binom{4}{1}\binom{3}{1}\binom{2}{1}\binom{1}{1} = \frac{13!}{2!1!4!2!1!1!1!1!}$$ distinguishable permutations.

However, if we simply add these two results, we will have counted permutations that include the subsequence UQU twice, once when we count permutations containing the subsequence QU and once when we count permutations containing the subsequence UQ. Therefore, we must subtract them from the total.

If a permutation of OBSEQUIOUSNESS contains the subsequence UQU, then we have a permutation of the $12$-element multiset $$\{2 \cdot O, 1 \cdot B, 4 \cdot S, 2 \cdot E, 1 \cdot UQU, 1 \cdot I, 1 \cdot N\}$$ of which there are $$\binom{12}{2}\binom{10}{1}\binom{9}{4}\binom{5}{2}\binom{3}{1}\binom{2}{1}\binom{1}{1} = \frac{12!}{2!1!4!2!1!1!1!}$$ distinguishable permutations.

By the Inclusion-Exclusion Principle, the number of distinguishable permutations of OBSEQUIOUSNESS in which Q and U are together is $$2 \cdot \frac{13!}{2!1!4!2!1!1!1!1!} - \frac{12!}{2!1!4!2!1!1!1!}$$

Method 2: We subtract the number of arrangements in which Q and U are not adjacent from the total number of arrangements.

We showed above that the number of distinguishable permutations of the letters of the word OBSEQUIOUSNESS is $$\frac{14}{2!1!4!2!1!2!1!1!}$$ From these, we must subtract those arrangements in which Q and U are not adjacent.

To count arrangements in which Q and U are not adjacent, we first remove the letters Q, U, and U from the word OBSEQUIOUSNESS, then insert the letters Q, U, and U so that Q is not adjacent to a U.

If we remove Q, U, and U from the word OBSEQUIOUSNESS, we are left with the multiset $$\{2 \cdot, 1 \cdot B, 4 \cdot S, 2 \cdot E, 1 \cdot I, 1 \cdot N\}$$ The letters in this multiset can be arranged in $$\binom{11}{2}\binom{9}{1}\binom{8}{4}\binom{4}{2}\binom{2}{1}\binom{1}{1} = \frac{11!}{2!1!4!2!1!1!}$$ distinguishable ways.

For a given arrangement of these eleven letters, there are twelve spaces in which we could place the Q and two Us, ten between successive letters and two at the ends of the row.
$$\square O \square B \square S \square E \square I \square O \square S \square N \square \square E \square S \square S \square$$

Arrangements of the letters of the word OBSEQUIOUSNESS in which Q, U, and U are separated: To ensure that Q, U, and U are separated, we choose one of the twelve spaces for the Q and two of the remaining eleven spaces for the two Us. Hence, there are $$\binom{12}{1}\binom{11}{2} \cdot \frac{11!}{2!1!4!2!1!1!}$$ distinguishable arrangements of the letters of the word OBSEQUIOUSNESS in which the letters Q, U, and U are separated.

We have not yet removed all the arrangements in which Q is not adjacent to a U since those arrangements include those in which the two Us are consecutive but not adjacent to Q.

Arrangements of the letters of the word OBSEQUIOUSNESS in which the Us are together but separated from the Q: We choose one of the twelve spaces for the Q and one of the remaining eleven spaces for the UU. Hence, there are $$\binom{12}{1}\binom{11}{1} \cdot \frac{11!}{2!1!4!2!1!1!}$$ such arrangements.

Hence, the number of admissible arrangements is $$\frac{14!}{2!1!4!2!1!1!} - \binom{12}{1}\binom{11}{2} \cdot \frac{11!}{2!1!4!2!1!1!} - \binom{12}{1}\binom{11}{1} \cdot \frac{11!}{2!1!4!2!1!1!}$$