7
$\begingroup$

Find the number of ways of arranging the letters $\text{AAAAA, BBB, CCC, D, EE & F}$ in a row if no two $\text{C's}$ are together?

My Attempt:

Well, I should I arrive at the answer if I subtract the cases where 3 $\text{C's}$ and 2 $\text{C's}$ appear together from the total.

Total possibilities $= \frac{15!}{5!3!3!2!}$

Total possibilities where 3 $\text{C's}$ appear $=\frac{13!}{5!3!2!}$

However, I am not able to find the possibilities for 2 $\text{C's}$ being together and get to the answer.

Any help would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ I'd try to find all arrangements of non–C letters, then splitting each sequence into four groups (with the first one and last one possibly empty). $\endgroup$ – CiaPan Mar 12 '18 at 12:02
6
$\begingroup$

While I prefer the approach explained by Alaleh A and Parcly Taxel, here is how you can solve the problem using the Inclusion-Exclusion Principle.

The number of distinguishable arrangements of $5$ A's, $3$ B's, $3$ C's, $1$ D, $2$ E's, and $1$ F is $$\frac{15!}{5!3!3!1!2!1!}$$ as you found.

From these, we must subtract those arrangements in which a pair of C's are adjacent.

A pair of C's are adjacent: We have $14$ objects to arrange, $5$ A's, $3$ B's, $1$ CC, $1$ C, $1$ D, $2$ E's, and $1$ F. They can be arranged in $$\frac{14!}{5!3!1!1!1!2!1!}$$ ways.

However, if we subtract $\frac{14!}{5!3!1!1!1!2!1!}$ from the total, we will have subtracted too much since we will have subtracted each arrangement with two pairs of adjacent C's twice (such arrangements have three consecutive C's), once when we designated the first two C's as the adjacent pair and once when we designated the last two C's as the adjacent pair. Since we only want to subtract such arrangements once, we must add them back.

Two pairs of adjacent C's: As mentioned above, this means the three C's are consecutive. Hence, we have $13$ objects to arrange, $5$ A's, $3$ B's, $1$ CCC, $1$ D, $2$ E's, and $1$ F. The number of such arrangements is $$\frac{13!}{5!3!1!1!2!1!}$$ as you found.

Hence, the number of arrangements of $5$ A's, $3$ B's, $3$ C's, $1$ D, $2$ E's, and $1$ F in which no two C's are consecutive is $$\frac{15!}{5!3!3!1!2!1!} - \frac{14!}{5!3!1!1!2!1!} + \frac{13!}{5!3!1!1!2!1!}$$

$\endgroup$
14
$\begingroup$

Ignore the C's for the moment and arrange the remaining letters. There are $\frac{12!}{5!3!2!}=332640$ ways to do this.

Now consider the thirteen spaces between and beyond the letters – at most one C may be inserted into each space, so given an arrangement of the other letters there are $\binom{13}3=286$ ways to add C's.

The total number of admissible combinations is thus $332640×286=95135040$.

$\endgroup$
7
$\begingroup$

Try a simpler approach, start with counting he number of ways you can arrange all letters except C's. it's:

$$ \frac{12!}{5!3!2!}$$

now there are 13 places to put the C's where they won't be next to each other so the answer is:

$$\frac{12!}{5!3!2!} \binom{13}{3}$$

$\endgroup$
2
$\begingroup$

Let $n_1$ be all letters except C ($=12$)and $n_2$ be Cs ($=3$). I am going to generalize the solution in such a manner that you have no two C's together (p=0), two C's together (p=1) and three C's together (p=2)

Each pair must have a left-hand member, which we can choose from any of the Cs except the last: $\tbinom{n_2-1}{p}$. This will create $n_2-p$ blocks of Cs, which we can distribute into the $n_1+1$ slots between and around the non-Cs: $\tbinom{n_1+1}{n_2-p}$. Thus the number of arrangemenets with exactly $p$ pairs is $\tbinom{n_2-1}{p}\tbinom{n_1+1}{n_2-p}.\frac{n_1!}{5!.3!.2!}$

For p = 0 in the question

$$\tbinom{3-1}{0}\tbinom{12+1}{3-0}.\frac{12!}{5!.3!.2!}$$

$$\tbinom{2}{0}\tbinom{13}{3}.\frac{12!}{5!.3!.2!}$$

$\endgroup$
-3
$\begingroup$

First arrange all the letters without $C$'s, i.e. $$\frac{12!}{5!3!1!2!1!}.$$ Now we have to fill inside the gaps between arranged letters. As they given no two $C$'s come together, means $3$ $C$'s also doesn't come together. The answer: $$ \frac{12!}{5!3!1!2!1!}*\frac{P^{13}_3}{3!}. $$ For example I have $3$ chocolates, that doesn't mean that I don't have $2$.

$\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.