Number of ways to arrange word 'KBCKBCKBC'

Question

The word 'KBCKBCKBC' is to be arranged in a row such that no word contains the pattern of KBC.

$Attempt$

Event $A$=1st KBC is in the pattern, $B$=2nd KBC is in the pattern and similar is the event C.

Now required is $n((notA) (notB) (notC)) =Total ways - [\sum n(A) - \sum n(AB)+ \sum n(ABC)] $

Total ways = $\frac{9!}{3!3!3!}$

$\sum n(AB) = \frac{5!}{2!}$

$\sum n(ABC) = 1$

But, my main doubt is that I am not able calculate $\sum n(A)$.

Any suggestion? Also please suggest about different method you know.

Thanks for the help.

Answer 1

The number of valid words is \begin{align*} \frac{9!}{3!3!3!}-\frac{7!}{2!2!2!1!}+\frac{5!}{1!1!1!2!}-\frac{3!}{3!}=1\,680-630+60-1\color{blue}{=1\,109} \end{align*}

Comment:

• We consider words of length $9$ built from three groups $BBB,CCC,KKK$, resulting in $\frac{9!}{3!3!3!}$.

• We subtract all words which have at least one occurrence of $BCK$. We think of $BCK$ as a new character $X$. We consider words of length $7$ built from $4$ groups $BB,CC,KK,X$, resulting in $\frac{7!}{2!2!2!1!}$.

• We have subtracted strings with occurrences of two times $BCK$ more than once. As compensation we add all words which contain at least two times $BCK$. We think of $BCK$ as a new character $X$. We consider words of length $5$ built from $4$ groups $B,C,K,XX$, resulting in $\frac{5!}{1!1!1!2!}$.

• We have added strings with occurrences of three times $BCK$ more than once. As compensation we subtract all words which contain at least three times $BCK$. We consider words of length $3$ built from $1$ group $XXX$, resulting in $\frac{3!}{3!}$.

Answer 2

It seems you are considering only the three cases, when $KBC$ appears in the front, center and end. In fact, it may appear at other locations as noted by JMoravitz in the comment.

Let $A_1,A_2,...,A_7$ indicate the starting position of the block $KBC$. So, $A_1,A_4,A_7$ correspond to your cases $A,B,C$. Using inclusion-exclusion, the number of words with one, two or three word blocks $KBC$ is: $$|A_1|+|A_2|+|A_3|+|A_4|+|A_5|+|A_6|+|A_7|-\\ (|A_1A_4|+|A_1A_5|+|A_1A_6|+|A_1A_7|+|A_2A_5|+\\ |A_2A_6|+|A_2A_7|+|A_3A_6|+|A_3A_7|+|A_4A_7|)+\\ (|A_1A_3A_7|)=\\ 7\cdot \frac{6!}{(2!)^3}-10\cdot 3!+1=630-60+1=571.$$ Note: Many overlapping events such as $A_1A_2,A_1A_2A_3,A_1A_2A_3A_4,$ etc are dropped in the above expression and only the events with non-zero cardinality are preserved.

The total number of words is: $$\frac{9!}{(3!)^3}=1680.$$ Hence, the number of words without the word block $KBC$ anywhere in the $9$-letter word is: $$1680-571=1109.$$

Answer 3

This answer is based upon the Goulden-Jackson Cluster Method which is a convenient method to derive a generating function for problems of this kind.

We consider the set of words in $ \mathcal{V}^{\star}$ of length $n\geq 0$ built from an alphabet $$\mathcal{V}=\{B,C,K\}$$ and the set $\mathcal{B}=\{KBC\}$ of bad words, which are not allowed to be part of the words we are looking for.

We derive a function $F(x)$ with the coefficient of $x^n$ being the number of wanted words of length $n$ from the alphabet $\mathcal{V}$. According to the paper (p.7) the generating function $F(x)$ is \begin{align*} F(x)=\frac{1}{1-dx-\text{weight}(\mathcal{C})} \end{align*} with $d=|\mathcal{V}|=3$, the size of the alphabet and with the weight-numerator $\mathcal{C}$ with \begin{align*} \text{weight}(\mathcal{C})=\text{weight}(\mathcal{C}[KBC]) \end{align*}

We calculate according to the paper \begin{align*} \text{weight}(\mathcal{C}[KBC])&=-x^3 \end{align*}

It follows with some help of Wolfram Alpha \begin{align*} F(x)&=\frac{1}{1-dx-\text{weight}(\mathcal{C})}\\ &=\frac{1}{1-3x+x^3}\\ &=1 + 3 x + 9 x^2 + 26 x^3 + 75 x^4 + 216 x^5+622 x^6 \\ &\qquad+ 1\,791 x^7 + 5\,157 x^8 + \color{blue}{14\,849} x^9+42\,756 x^10 +\cdots\tag{1}\\ \end{align*}

Denoting with $[x^n]$ the coefficient of $x^n$ in a series we see in (1) there are $\color{blue}{14\,849}$ words of length $9$ which do not contain the string $KBC$.

We want to find all words which have exactly three occurrences of each of the letters $B,C,K$. In order to find this number we have to keep track of the letters in the generating function $F(x)$. We do so be setting \begin{align*} \color{blue}{G(x)}&\color{blue}{=\frac{1}{1-(B+C+K)x+(BCK)x^3}} \end{align*} and we obtain by extracting the coefficient of $B^3C^3D^3x^9$ of $G(x)$ again with some help of Wolfram Alpha \begin{align*} [B^3C^3D^3t^9]G(x)\color{blue}{=1\,109} \end{align*}

Note this example is relatively simple, since we have only one bad word and this word has no overlapping. A situation with a bad word with overlapping for instance with $BCB$ is harder to calculate and in such cases this method shows more of its power.