How many 12-letter words are there with no block $5 \times a$, $4 \times b$ and $3 \times c$

58 Views Asked by At

We arrange 12-letter words having at our disposal five letters $a$, four letters $b$ and three letters $c$. How many words are there without any block $5 \times a$, $4 \times b$ and $3 \times c$. I need to use inclusion - exclusion principle. I counted all possible 12 letter words - $\frac{12!}{5!4!3!}$. Then words with block of letters:

only $a$ blocks - $8\cdot \frac{7!}{4!3!}$

only $b$ blocks - $9\cdot \frac{8!}{5!3!}$

only $c$ blocks - $10\cdot \frac{9!}{5!4!}$.

Now I have to count all words, where block: $a,b$ or $a,c$, or $b,c$ appears together, but I don't now how.

1

There are 1 best solutions below

0
On BEST ANSWER

If we let $N$ denote the total number of distinguishable arrangements of $aaaaabbbbccc$, $A$ denote the set of permutations with five consecutive $a$s, $B$ denote the set of permutations with four consecutive $b$s, and $C$ denote the set of permutations with three consecutive $c$s, then, by the Inclusion-Exclusion Principle, the number of arrangements with no block of five consecutive $a$s or four consecutive $b$s or three consecutive $c$s is \begin{align*} |A' \cap B' \cap C'| & = N - |A \cup B \cup C|\\ & = N - (|A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|)\\ & = N - |A| - |B| - |C| + |A \cap B| + |A \cap C| + |B \cap C| - |A \cap B \cap C| \end{align*}

You have correctly calculated $N$, $|A|$, $|B|$, and $|C|$.

$|A \cap B|$: We have five objects to arrange: $aaaaa$, $bbbb$, $c$, $c$, $c$. There are $\binom{5}{3}$ ways to select three of the five positions for the three $c$s and $2!$ ways to arrange the remaining two distinct objects in the remaining two positions. Hence, there are $$\binom{5}{3}2! = \frac{5!}{3!}$$ such arrangements.

Alternatively, arrange the three $c$s in a line. This creates four spaces in which we can place the block $aaaaa$, two between successive $c$s and two at the ends of the row. $$\square c \square c \square c \square$$ Once we have placed the block $aaaa$, we have four objects in a row, which creates five spaces in which to place the block $bbb$, three between successive objects and two at the ends of the row. Hence, $$|A \cap B| = 4 \cdot 5$$

Can you finish the argument by counting $|A \cap C|$, $|B \cap C|$, and $|A \cap B \cap C|$?