5
$\begingroup$

If you have patience please read through the whole post. I have made clear what was my line of thought for each step that I did.

Problem Statement:-

How many words of seven letters formed by the letters of the word $\text{SUCCESS}$ so that

$\text{(i)}$ the two $\text{C's}$ are together but not the two $\text{S's}$.

$\text{(ii)}$ neither the two $\text{C's}$ nor the two $\text{S's}$ are together.


My Attempt at a solution:-

$\text{(i) Part - 1}$

  • $\text{1}^\text{st}$ Approach:-

Since we have to arrange the letters in such a way that the $\text{C's}$ occur together but the $\text{S's}$ don't, so we first combine the two $\text{C's}$ together into one entity, reducing the total letters(or entities) to $6$. Since the $\text{S's}$ shouldn't occur consecutively(that's what I infer from the "the two \text{S's} should not be together" part in the question") we first arrange the remaining letters(or entities) which are $\{\text{U,CC,E}\}$.

$$\_\;\text{U}\;\_\;\text{CC}\;\_\;\text{E}\;\_$$

After arranging these letters we see that there are $4$ gaps in which the $3 \text{ S's}$ can be arranged so that none of the $\text{S's}$ are together, also the letters that were arranged before the $\text{S's}$ can be arranged among themselves in $3!$ ways.

So, the total number of ways in which we can arrange the given letters so that the two $\text{C's}$ occur together but no two $\text{S's}$ occur together$=\displaystyle\binom{4}{3}\cdot3!=24$

But the textbook gives the answer as $12$.

Now, just to check whether my first attempt for the $\text{1}^\text{st}$ part of the question was correct or not I decided to approach it differently.

  • $\text{2}^\text{nd}$ Approach:-

Number of ways in which the two $\text{C's}$ occur together$=\dfrac{6!}{3!}$

Since no two $\text{S's}$ must occur together, hence

The number of ways in which no two $\text{C's}$ and no two $\text{S's}$ occur together$=\text{Total number of permutations $-$ Number of ways in which two $\text{C's}$ and two $\text{S's}$ occur together}$

Now, lets find the number of ways in which two $\text{S's}$ and two $\text{C's}$ occur together. The number of ways will be that in which we group two $\text{C's}$ and two $\text{S's}$ into, say, one super $\Bbb{C}$ and one super $\Bbb{S}$. So, we have to arrange $\{\text{S,U,$\Bbb{C}$,E,$\Bbb{S}$}\}$, which can be done in $5!$ ways.

After starting out on working on this approach I found that there is a little confusion that I have that whether three $\text{S's}$ could occur together or not.

If they can, then we have to exclude the permutation in which three $\text{S's}$ and two $\text{C's}$ occur together simultaneously from the permutation of two $\text{C's}$ and two $\text{S's}$ (so that they maybe counted in the total count) which is given by $4!$.

So, the number of ways in which no two $\text{C's}$ and no two $\text{S's}$ occur together becomes $$\dfrac{6!}{3!}-(5!-4!)=24$$.

But, if the three $\text{S's}$ cannot occur together then, we have the permutation of the letters under the assumed condition as $$\dfrac{6!}{3!}-5!=0$$

This approach turned out to be more confusing considering how I got $0$ ways when the three $\text{S's}$ cannot occur together which I think is not correct, because a simple counter example is $\text{SUSCCES}$.

$\text{(ii) Part - 2}$

  • $\text{1}^\text{st}$ Approach:-

In this Approach I used the number of ways in which the two $\text{C's}$ occur together but not the two $\text{S's}$, so this can also act as the verification for the answer of the $1^\text{st}$ part.

First, we will find the number of ways in which the two $\text{S's}$ don't occur together, which can be found by the gap method as follows $$\_\;\text{U}\;\_\;\text{C}\;\_\;\text{C}\;\_\;\text{E}\;\_$$

Since we have $5$ gaps, so the $3\text{ S's}$ can be placed in $\binom{5}{3}$ ways followed by the arrangement of the prearranged letters in $\dfrac{4!}{2!}$. So, we get the number of ways in which the two $\text{S's}$ don't occur together as $$\binom{5}{3}\cdot\dfrac{4!}{2!}=120$$

Now, from this we exclude the number of ways in which the two $\text{C's}$ occur together with the two $\text{S's}$ not occurring together simultaneously, which is given by:-

  1. if we consider the first approach of the first part of the question, and the first assumption of the second approach, as correct then$=\displaystyle\binom{4}{3}\cdot3!=24$
  2. If we consider the second assumption of the second approach of the first part as correct, then $0$ (well lets leave this one, we already know there is some blunder in there that I have done)

So, the total number of ways in which neither the two $\text{C's}$ nor the two $\text{S's}$ are together=$$\binom{5}{3}\cdot\dfrac{4!}{2!} - \displaystyle\binom{4}{3}\cdot3!=120-24=\boxed{96}$$

Viola, the answer of the second part is correct, so the book gives the wrong answer for the first part.

Now, considering the book gave the wrong answer and the first assumption of the second approach in the first part was correct(yeah, this looks like a maze to me now to indicate all this XD), I thought of applying some PIE for my second method.

  • $\text{2}^\text{nd}$ Approach:-

Since this approach is inspired by the first assumption in 2nd approach for the first part, so I assumed that what the problem implies by the statement "the two $\text{S's}$ are together" is that only two of the $\text{S's}$ should occur together at a time.

So, consider the following sets $$A\rightarrow \text{All the permutations that include two C's together}\\ B\rightarrow \text{All the permutations that include only two S's together}$$

So, $$|A|=\dfrac{6!}{3!}=120\\ |B|=\dfrac{6!}{2!}(\rightarrow\text{two S's occur together})-\dfrac{5!}{2!}(\rightarrow\text{three S's occur together})=300\\ |A\cap B|=5!(\rightarrow\text{two C's and two S's occur together simultaneously})-4!(\rightarrow\text{two C's and three S's ocurr together simultaneously})=96$$

Now, as per PIE, we have $$|A\cup B|=|A|+|B|-|A\cap B|=120+300-96=420-96$$

Now, $\left(A\cup B\right)^c=\left(A^c\cap B^c\right)$, and $\left(A^c\cap B^c\right)\implies \text{two C's don't occur together and two S's don't occur together}$ $$\|(A\cup B)^c|=|(A^c\cap B^c)|=\dfrac{7!}{3!\times2!}-|A\cup B|=420-(420-96)=\boxed{96}$$


Conclusion: What bugs me.

  • What's wrong with the second assumption of the second approach in the answer to the first part of the question that I am getting $0$ as the answer given that I have already shown a counter example that tells that there are infact more than $0$ ways.

  • I find the language of the question quite confusing. The "the two $\text{S's}$" part confuses me the most. How does it mean that only two of the $\text{S's}$ should occur together and not three of them. In my opinion, the mention of the THE in "THE two $\text{S's}$" tells that only those two $\text{S's}$ should come together that were initially together in the word $\text{SUCCESS}$ were the $\text{S's}$ considered to be different, but as the S's are indistinguishable so that makes the statement "only two of the three $\text{S's}$ should occur together".

  • Lastly, I found the same question as the second part of the question and one of the solutions though looked very lucrative, I can't seem to understand how it was formulated, if you think that it can be understood by a student having knowledge of highschool mathematics and what I consider to be a little knowledge of engineering mathematics then, can you enlighten me as to how it was formulated.

$\endgroup$
  • $\begingroup$ What do you mean "are can together"??? Are they allowed to be together, or do they have to be together? $\endgroup$ – barak manos Dec 29 '16 at 8:13
  • $\begingroup$ I wrote the exact statement in the book, and thanks for pointing that out I will be mentioning that in the Conclusion part of my post(forgot to mention that). For your convenience though I interpreted it as "$\text{are can}\rightarrow\text{occur together}$". Yeah I was pretty confused about it too and thought that there are two possible interpretations that you mention. $\endgroup$ – user350331 Dec 29 '16 at 8:15
  • $\begingroup$ Well, I can solve it as is, if you'd like that. Reading throughout your question seems rather tedious... $\endgroup$ – barak manos Dec 29 '16 at 8:17
  • $\begingroup$ I just wrote that because I have pointed out where I am erring and what was my line of thought when I erred. If you want you can see where I erred from the conclusion part. $\endgroup$ – user350331 Dec 29 '16 at 8:20
  • 1
    $\begingroup$ I would hardly consider "are can together" as confusing language. It is pretty outright "wrong language". $\endgroup$ – barak manos Dec 29 '16 at 8:28
2
$\begingroup$

The phrasing of the question is atrocious. Let's assume the intended question was

How many words can be formed from the letters of the word SUCCESS if

  1. the two C's are together but no two of the three S's are together?
  2. no two adjacent letters are identical?

Your first solution to the first question is correct. The book's answer is incorrect.

As for your second solution, we need to exclude those arrangements in which consecutive S's appear. Notice that when you subtract the $5!$ arrangements in which two S's are together, you subtract arrangements in which all three S's are together twice, once when you count arrangements in which the first two of the three consecutive S's are counted as your double S and once when you count arrangements in which the last two of the three consecutive S's are counted as your double S. Consequently, when you apply the Inclusion-Exclusion Principle, you must add the $4!$ arrangements in which three consecutive S's appear so that arrangements in which three consecutive S's appear are only excluded once. That yields $$\frac{6!}{3!} - 5! + 4!$$ which equals the answer
$$\frac{6!}{3!} - (5! - 4!)$$ you obtained when you assumed that three consecutive S's could not appear.

As for the second question, which you also solved correctly, here are two approaches.

First approach: Consider cases.

There are $3!$ arrangements of U, CC, E, where the double C is treated as a single letter. To ensure that no two identical letters are consecutive, we must insert an S between the two C's. Suppose we have an arrangement of the form $$UCSCE$$
To ensure that the S's are separated, we must place the two remaining S's in one of the four spaces indicated by a wedge $$\wedge U \wedge C S C \wedge E \wedge$$ There are $$3!\binom{4}{2} = 36$$ distinguishable arrangements of the letters of SUCCESS in which no two consecutive letters are identical and the two C's are separated by a single S.

In the remaining arrangements, the C's must be separated by a letter other than a single S. There are $2!$ arrangements of the letters U and E, which creates three gaps in which we can place the two C's.
$$\wedge U \wedge E \wedge$$ Since we can fill two of these three gaps in $\binom{3}{2}$ ways, there are $$2! \cdot \binom{3}{2} = 3!$$ arrangements of U, C, C, E in which the two C's are separated. Suppose we have an arrangement such as $$C U C E$$ To ensure the three S's are also separated, we must place an S in three of the five locations indicated by a wedge $$\wedge C \wedge U \wedge C \wedge E \wedge$$ Hence, there are $$2!\binom{3}{2}\binom{5}{3} = 60$$ arrangements of the letters of SUCCESS in which no two letters are identical and the C's are separated by a letter other than a single S.

Since the cases are disjoint, there are $$3!\binom{4}{2} + 2!\binom{3}{2}\binom{5}{3} = 36 + 60 = 96$$ arrangements of the letters of the word SUCCESS in which no two consecutive letters are identical.

Second approach: We can apply the Inclusion-Exclusion Principle by considering pairs of identical letters. The total number of distinguishable arrangements of the seven letters of the word SUCCESS is $$\frac{7!}{3!2!}$$ where the $3!$ in the denominator represents the number of ways we could permute the three S's within a given arrangement without producing an arrangement that is distinguishable from the given arrangement and the $2!$ in the denominator represents the number of ways we could permute the two C's within a given arrangement without producing an arrangement that is distinguishable from the given arrangement.

We now exclude arrangements in which pairs of identical letters are adjacent.

One pair of adjacent identical letters

A pair of consecutive C's: Treat the double C as a single letter, so we are arranging the six objects S, S, S, U, E, CC, which can be done in $$\frac{6!}{3!}$$ distinguishable ways.

A pair of consecutive S's: Treat a double S as a single letter, so we are arranging the six objects SS, S, U, E, C, C, which can be done in $$\frac{6!}{2!}$$ distinguishable ways.

Two pairs of identical letters

A pair of consecutive C's and a pair of consecutive S's: We must arrange CC, SS, S, U, E, which can be done in $$5!$$ ways.

Two pair of consecutive S's: Since there are only three S's in SUCCESS, the two pairs of consecutive S's must be a block of three consecutive S's. Thus, we must arrange the five objects SSS, C, C, U, E, which can be done in $$\frac{5!}{2!}$$ distinguishable ways.

Three pairs of consecutive identical letters

A pair of consecutive C's and two pairs of consecutive S's: This can only occur if there is a double C and a triple S, so we must arrange the four objects CC, SSS, U, E, which can be done in $$4!$$ distinguishable ways.

By the Inclusion-Exclusion Principle, the number of distinguishable arrangements of the letters of the word SUCCESS in which no two consecutive letters are identical is
$$\frac{7!}{2!3!} - \frac{6!}{3!} - \frac{6!}{2!} + 5! + \frac{5!}{2!} - 4! = 96$$ The answer to which you linked requires a much deeper knowledge of mathematics than that described in your post.

$\endgroup$
  • $\begingroup$ How do you suppose this-"Notice that when you subtract the $5!$ arrangements in which two S's are together, you subtract arrangements in which all three S's are together twice, once when you count arrangements in which the first two of the three consecutive S's are counted as your double S and once when you count arrangements in which the last two of the three consecutive S's are counted as your double S."Becasue I think that the $\text{S's}$ are indistinguishable hence they are not permuted among each other. And, going by your supposition that there are two sets of two $\text{S's}$(cont.) $\endgroup$ – user350331 Dec 30 '16 at 2:19
  • $\begingroup$ (cont.) together(which I refer to $\Bbb{S}$ in my post), so then by your logic there should be three possible $\Bbb{S}$ together considering that you forgot the $\Bbb{S}$ which we get when we consider the first and the last $\Bbb{S}$ together to form the $\Bbb{S}$ $\endgroup$ – user350331 Dec 30 '16 at 2:20
  • $\begingroup$ +1 Your first approach to the second problem does make me feel a little relaxed as I dont know what made me answer the question what I was thinking wrong about the three S's coming together $\endgroup$ – user350331 Dec 30 '16 at 2:33
  • 1
    $\begingroup$ Notice that in the inclusion-exclusion arguments, I am excluding arrangements with consecutive identical letters. Thus, an arrangement with three consecutive S's is counted twice. We count $$CUCESSS$$ once when we designate the first two S's as a double S and once when we designate the last two S's as the double S. However, we do not count the first and third S's as a double S since they are not consecutive, just as we would not count $CUCESSS$ as a double C. $\endgroup$ – N. F. Taussig Dec 30 '16 at 14:15
  • $\begingroup$ Hmm...so that was the case. $\endgroup$ – user350331 Dec 31 '16 at 0:55
1
$\begingroup$

So, first of all, your answer to the first question is correct; it should most certainly be 24. The only way it could not be 24 is if the question somehow meant to imply that the S's were distinguishable, and only the latter 2 are restricted from being together. But in that case, the possible permutations would contain as a subset the permutations in which none of the 3 S's are together, so then the answer would be GREATER than 24. So, no matter our interpretation, the answer could in no way be 12, and the textbook must have a typo answer. Given that, it only really makes sense to presume that the S's are indistinguishable, and so the answer is indeed 24 (if you have any doubt, you can easily list the 24 permutations in which no two S's occur together). What's more, as far as I can tell, your methodology in approaching the second question is completely correct.

The issue you're having is that you've confused yourself regarding this question of the three S's occurring together. The problem restricts two S's being adjacent, which clearly also restricts all three from being adjacent (note that your first approach certainly makes this restriction). But your second approach to the first problem seems to say that there are no permutations in which no three S's are together.

To see where the mistake was made, let's return to the question of the number of permutations of the alphabet {S,U,$\Bbb{C}$,E,$\Bbb{S}$}. Were the letters of this alphabet truly independent, there would be $5!$ permutations, as you say (and then subsequently conclude that the answer to the first question is $0$). The problem is that S$\Bbb{S}$ is identical to $\Bbb{S}$S, but the $5!$ answer counts these as distinct-- that is, $5!$ double counts the case of all three S's occurring together. So, to count the unique orderings of {S,U,$\Bbb{C}$,E,$\Bbb{S}$}, we have to take $5!$ minus the number of ways all three S's can occur together. THIS is the reason we subtract $4!$, NOT because we're allowing the final answer to include permutations which have all three S's together. If we were to allow the final answer to include such permutations, we would have to subtract the $4!$ twice-- once to negate the double counting, and then again to remove the term entirely.

Regarding the last bullet point, I don't believe there's a way to easily and directly see the relationship between the coefficients of the polynomials $q_k(x)$ and the problem of alphabet permutations with no two adjacent letters identical-- it's just a matter of proving the equivalence. In that respect, I wouldn't say it's strictly beyond the scope of a high school student familiar with integral calculus, but I don't expect it's trivial, either (I haven't attempted the algebra myself). If it helps the formula make more sense, the integral with the exponential function is relevant due to the identity $\Gamma(k)=\int_0^\infty x^ke^{-x}dx=k!$ for $k\in\Bbb{N}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.